题干：

During the War of Resistance Against Japan, tunnel warfare was carried out extensively in the vast areas of north China Plain. Generally speaking, villages connected by tunnels lay in a line. Except the two at the ends, every village was directly connected with two neighboring ones. 

Frequently the invaders launched attack on some of the villages and destroyed the parts of tunnels in them. The Eighth Route Army commanders requested the latest connection state of the tunnels and villages. If some villages are severely isolated, restoration of connection must be done immediately! 

Input

The first line of the input contains two positive integers n and m (n, m ≤ 50,000) indicating the number of villages and events. Each of the next m lines describes an event. 

There are three different events described in different format shown below: 

D x: The x-th village was destroyed. 

Q x: The Army commands requested the number of villages that x-th village was directly or indirectly connected with including itself. 

R: The village destroyed last was rebuilt. 

Output

Output the answer to each of the Army commanders’ request in order on a separate line. 

Sample Input

7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4

Sample Output

1
0
2
4

题目大意：

D代表破坏村庄，R代表修复最后被破坏的那个村庄，Q代表询问包括x在内的最大连续区间是多少

解题报告：

    区间合并  + 单点更新 + 区间查询（最长覆盖区间查询）。用栈来记录 修复 的顺序。

AC代码：

#include<bits/stdc++.h>

using namespace std;
const int MAX = 50000 + 5;
struct TREE {
	int l,r;
	int left,right,all;
	int laz;
} tree[4*MAX];
stack<int > sk;

void modify(int cur,int val) {
	tree[cur].left = tree[cur].right = tree[cur].all = val;
}
//void pushup(int cur) {
//	if(tree[cur*2].left == tree[cur*2].r - tree[cur*2].l + 1) tree[cur].left = tree[cur*2].left + tree[cur*2+1].left;
//	else tree[cur].left = tree[cur*2].left;
//	if(tree[cur*2+1].right == tree[cur*2+1].r - tree[cur*2+1].l + 1) tree[cur].right = tree[cur*2+1].right + tree[cur*2].right;
//	tree[cur].all = max( tree[cur*2].right + tree[cur*2+1].left, max( tree[cur*2].all,tree[cur*2+1].all ) );
//}	
void pushup(int cur) {
	tree[cur].left = tree[cur*2].left;
	if(tree[cur].left/*也可以写tree[cur*2].left*/== tree[cur*2].r - tree[cur*2].l + 1) tree[cur].left +=tree[cur*2+1].left; //这里是cur*2+1！！不是cur*2 
	tree[cur].right = tree[cur*2+1].right;
	if(tree[cur].right == tree[cur*2+1].r - tree[cur*2+1].l + 1) tree[cur].right += tree[cur*2].right;
	tree[cur].all = max(tree[cur*2].right + tree[cur*2+1].left,max(tree[cur*2].all,tree[cur*2+1].all));//这里必须用tree[cur*2].all,tree[cur*2+1].all)，不能用left和right！ 
	
}
void build(int l,int r ,int cur) {
	tree[cur].l = l;
	tree[cur].r = r;
	tree[cur].laz = -1;
	if(l == r) {
		tree[cur].all = tree[cur].left = tree[cur].right = 1;
		return ;
	}
	int m = (l+r)/2;
	build(l,m,cur*2);
	build(m+1,r,cur*2+1);
	pushup(cur);
}
void update1(int tar,int val, int l,int r,int cur) {
	if(l == r) {
		modify(cur,val);
		tree[cur].laz = val;
		return ;
	}
	int m = (l+r)/2;
	if(tar <=m) update1(tar,val,l,m,cur*2);
	else update1(tar,val,m+1,r,cur*2+1);
	pushup(cur);
}
int query(int tar,int l,int r,int cur) {
	if(l == r ) return tree[cur].left;//是all和是 
//		if(l == r || tree[cur].all == 0 || tree[cur].all == tree[cur].r-tree[cur].l + 1) return tree[cur].all;
//	pushdown(tree[cur].l,tree[cur].r,cur);
	int res = 0,tmp1 = 0,tmp2 = 0,tmp3 = 0;
	int m = (l+r)/2;
//	if(tar <= m) res += query(tar,l,m,cur*2);
//	if(tar >= m+1) res += query(tar,m+1,r,cur*2+1);
//	return res;
	if(tar <=m) {
		if(tar >= tree[cur*2].r-tree[cur*2].right + 1) return tree[cur*2].right + tree[cur*2+1].left;
		else return query(tar,l,m,cur*2);
	}
	else {
		if(tar <= tree[cur*2+1].l + tree[cur*2+1].left -1) return tree[cur*2+1].left + tree[cur*2].right;
		else return query(tar,m+1,r,cur*2+1);
	}
	
	
}
int main()
{
	int n,m;
	int tmp;
	char op[3];
	while(~scanf("%d%d",&n,&m) ) {
		while(!sk.empty() ) sk.pop();
		build(1,n,1);//0摧毁，1修复 
		while(m--) {
			scanf("%s",op);
			if(op[0] == 'D') {
				
				scanf("%d",&tmp);
				update1(tmp,0,1,n,1);
				sk.push(tmp);
			}
			else if(op[0] == 'R') {
				if(sk.empty() ) continue;
				tmp = sk.top();
				sk.pop();
				update1(tmp,1,1,n,1);
			}
			//询问 
			else {
				scanf("%d",&tmp);
				int x = query(tmp,1,n,1);
//				printf("%d   %d   %d\n",tree[3].left,tree[3].right,tree[3].all);
				printf("%d\n",x);
			}
			
		} 
	}
	return 0 ;
 } 
 //19:30