[JSOI2008]最大数MAXNUMBER

思路一： 直接上线段树，这个没什么好讲的，线段树最基本的操作

思路二： 单调栈+二分 这里上单调栈是一个很妙的地方，我们可以始终维护出一个线型递减的关系

二分即二分我们的目标区间左端在那个区间里，返回区间的右界就好

思路三： 单调栈+并查集 这里的并查集使用又是在二分上的一个优化，同样是用单调栈先维护出来分段的区间 但是在单调栈维护区间的同时，对每个节点的父亲进行维护

这样就可以完美的以o(n)的复杂度完成

整个思路很妙的在于（只是我之前每学习过罢了），用数组来模拟栈这个做法，一个数组来作存放元素的栈，一个数组来作存放下标的栈，这样就可以完美解决不方便直接访问栈内元素的问题。

附一个思路二代码：

using namespace std;
int m, d, w, l_ans, cnt, top;
inline int read() {
	int x = 0, f = 1;
	char c = getchar();
	while (c < '0' || c>'9') { if (c == '-') f = -1; c = getchar(); }
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}
const int N= 200005;
int que[2][N];
void add(int jk) {
	cnt++;
	while (top > 0 && jk > que[0][top]) {
		que[0][top] = 0;
		que[1][top--] = 0;
	}
	
	que[0][++top] = jk;
	que[1][top] = cnt;
}
int query(int jk, int l, int r) {
	while (l < r) {
		int mid = (l + r) / 2;
		if (jk > que[1][mid])
			l = mid + 1;
		else r = mid;
	 }
	return que[0][r];
}

int main() {
	m = read(); d = read();
	
	while (m--) {
		char flag=getchar();
		while (flag != 'A' && flag != 'Q') flag = getchar();
		if (flag == 'A')
			add((read() + l_ans) % d);
		else {
			l_ans = query(cnt - read() + 1, 1, top);
			cout << l_ans << endl;
		}
	}

	return 0;
}