[JSOI2008]最大数maxnumber

Description

BZOJ1012

Solution

线段树模板题

（话说vim的ggyG竟然不复制最后一个字符，送来了我bzoj的第一个ce...看来文末换行符还是要打的）

Code

#include <cstdio>
#include <algorithm>

typedef long long LL;
const int N = 800000 + 10;

LL a[N];

void add(int o, int l, int r, int q, LL v) {
	if (l == r) {
		a[o] = v;
		return;
	}
	int mid = (l+r) >> 1;
	if (q <= mid) add(o<<1, l, mid, q, v);
	else add(o<<1|1, mid+1, r, q, v);
	a[o] = std::max(a[o<<1], a[o<<1|1]);	
}

LL query(int o, int l, int r, int ql, int qr) {
	if (ql <= l && qr >= r) {
		return a[o];
	}
	int mid = (l+r) >> 1;
	LL ans = 0;
	if (ql <= mid) ans = std::max(ans, query(o<<1, l, mid, ql, qr));
	if (qr > mid) ans = std::max(ans, query(o<<1|1, mid+1, r, ql, qr));
	return ans;	
}

int main() {
	LL m, d;
	scanf("%lld%lld", &m, &d);
	LL ans = 0, x, n = 0;
	char op[3];	
	for (int i = 1; i <= m; ++i) {
		scanf("%s%lld", op, &x);
		if (op[0] == 'A') add(1, 1, m, ++n, (x+ans)%d);
		else {
			ans = query(1, 1, m, n-x+1, n);
			printf("%lld
", ans);
		}
	}	
	return 0;
}

Note

据说这个题还可以用ST表来解决。