记录编号	184261	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008] 最大数	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	3.312 s
提交时间	2015-09-02 16:18:47	内存使用	25.00 MiB

#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("bzoj_1012.in");
ofstream fout("bzoj_1012.out");
#define cin fin
#define cout fout
#define int long long
const int MAXM(200001);
long long x, m, d, matrix[MAXM * 18], len, last, query(int, int, int, int, int);
char c;
void update(int, int, int, int, int);

main()
{
//	cout << sizeof(matrix) / 1024 / 1024 << endl;
	cin >> m >> d;
	for (int i = 0; i < m; ++i){
		cin >> c >> x;		
		if (c == 'A')
			update(++len, (x + last) % d, 1, m, 1);
		else{
			last = query(len - x + 1, len, 1, m, 1);
			cout << last << endl;
		}
	}
	fin.close();
	fout.close();
//	for (; ; );
}

void update(int po, int ve, int l, int r, int ro)
{
	if (l == r){
		matrix[ro] = ve;
		return;
	}
	int m = (l + r) >> 1;
	if (m >= po)
		update(po, ve, l, m, ro << 1);
	else
		update(po, ve, m + 1, r, ro << 1 | 1);
	matrix[ro] = max(matrix[ro << 1], matrix[ro << 1 | 1]);
}

long long query(int ll, int rr, int l, int r, int ro)
{
	if (ll <= l && rr >= r)
		return matrix[ro];
	int m = (l + r) >> 1;
	long long re = 0;
	if (ll <= m)
		re = max(re, query(ll, rr, l, m, ro << 1));
	if (rr > m)
		re = max(re, query(ll, rr, m + 1, r, ro << 1 | 1));
	return re;
}