Codeforces 52C : Circular RMQ

問題文 : Circular RMQ

解法 :
Starry Sky木をそのまま実装すれば良い問題です.
ちなみに, Starry Sky木とは,
・区間[a, b]に値を加算する.
・区間[a, b]の(最大・最小)値を求める
の操作が同時に出来るようなデータ構造を指します.

この問題特有の「Circular」な部分は, [a, n]と[0, b]にわけてそれぞれの操作を行えば無問題です.

今回は, 2通りの方法で実装したものを紹介します. どちらも汎用性があるセグメント木なので, みなさんも好きな方を使ってみましょう.

①蟻本型(分離型セグメント木)
蟻本のSimple Problem with Integersのページで紹介されているように, 用途を分けたセグメント木で,
・その区間での最小値
・その区間に一様に加算される値
をもっておくセグメント木を構築します. add関数が肝です.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>

using namespace std;
typedef long long lint;

lint segMin[1 << 19], segAdd[1 << 19];
int n;

void add(int a, int b, int x, int k = 0, int l = 0, int r = n)
{
	if (r <= a || b <= l) return;
	
	if (a <= l && r <= b){
		segAdd[k] += x;
		while (k){
			k = (k - 1) / 2;
			segMin[k] = min(segMin[k * 2 + 1] + segAdd[k * 2 + 1], segMin[k * 2 + 2] + segAdd[k * 2 + 2]);
		}
		return;
	}
	
	add(a, b, x, k * 2 + 1, l, (l + r) / 2);
	add(a, b, x, k * 2 + 2, (l + r) / 2, r);
}

lint getMin(int a, int b, int k = 0, int l = 0, int r = n)
{
	if (r <= a || b <= l) return (LLONG_MAX);
	
	if (a <= l && r <= b) return (segMin[k] + segAdd[k]);
	
	lint left = getMin(a, b, k * 2 + 1, l, (l + r) / 2);
	lint right = getMin(a, b, k * 2 + 2, (l + r) / 2, r);
	
	return (min(left, right) + segAdd[k]);
	
}

int main()
{
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++){
		int t;
		scanf("%d", &t);
		add(i, i + 1, t);
	}
	
	int m;
	scanf("%d", &m);
	getchar();
	
	for (int i = 0; i < m; i++){
		int arg[3];
		char query[256], *p;
		int idx = 0;
		fgets(query, 256, stdin);
		
		p = strtok(query, " \n");
		while (p != NULL){
			arg[idx++] = atoi(p);
			p = strtok(NULL, " \n");
		}
		
		if (idx == 2){
			printf("%lld\n", arg[0] <= arg[1] ? getMin(arg[0], arg[1] + 1) : min(getMin(arg[0], n), getMin(0, arg[1] + 1)));
		}
		else {
			if (arg[0] <= arg[1]){
				add(arg[0], arg[1] + 1, arg[2]);
			}
			else {
				add(arg[0], n, arg[2]);
				add(0, arg[1] + 1, arg[2]);
			}
		}
	}
	
	return (0);
}

②遅延評価型セグメント木

kyuridenamidaさんのブログで紹介されている形のセグメント木です.
こちらは, evaluate関数が肝で, 他の関数はあまり意識せずに書いてもうまくいく事が多いです.
遅延評価については、きゅうりさんのブログに詳しく書かれているので, そちらを参照してください.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>

using namespace std;
typedef long long lint;

typedef struct {
	lint val;
	lint add;
} Node;

Node seg[1 << 19];
int n;

inline void evaluate(int idx)
{
	seg[idx].val += seg[idx].add;
	if (idx < (1 << 18) - 1){
		seg[idx * 2 + 1].add += seg[idx].add;
		seg[idx * 2 + 2].add += seg[idx].add;
	}
	
	seg[idx].add = 0;
}

void update(int k)
{
	seg[k].val = min(seg[k * 2 + 1].val, seg[k * 2 + 2].val);
}

void add(int a, int b, int x, int k = 0, int l = 0, int r = 1 << 18)
{
	evaluate(k);
	if (r <= a || b <= l) return;
	
	if (a <= l && r <= b){
		seg[k].add += x;
		evaluate(k);
		return;
	}
	
	add(a, b, x, k * 2 + 1, l, (l + r) / 2);
	add(a, b, x, k * 2 + 2, (l + r) / 2, r);
	update(k);
}

lint getMin(int a, int b, int k = 0, int l = 0, int r = 1 << 18)
{
	evaluate(k);
	if (r <= a || b <= l) return (LLONG_MAX);
	
	if (a <= l && r <= b){
		evaluate(k);
		return (seg[k].val);
	}
	
	lint left = getMin(a, b, k * 2 + 1, l, (l + r) / 2);
	lint right = getMin(a, b, k * 2 + 2, (l + r) / 2, r);
	update(k);
	
	return (min(left, right));
	
}

int main()
{
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++){
		int t;
		scanf("%d", &t);
		add(i, i + 1, t);
	}
	
	int m;
	scanf("%d", &m);
	getchar();
	
	for (int i = 0; i < m; i++){
		int arg[3];
		char query[256], *p;
		int idx = 0;
		fgets(query, 256, stdin);
		
		p = strtok(query, " \n");
		while (p != NULL){
			arg[idx++] = atoi(p);
			p = strtok(NULL, " \n");
		}
		
		if (idx == 2){
			printf("%lld\n", arg[0] <= arg[1] ? getMin(arg[0], arg[1] + 1) : min(getMin(arg[0], n), getMin(0, arg[1] + 1)));
		}
		else {
			if (arg[0] <= arg[1]){
				add(arg[0], arg[1] + 1, arg[2]);
			}
			else {
				add(arg[0], n, arg[2]);
				add(0, arg[1] + 1, arg[2]);
			}
		}
	}
	
	return (0);
}