这种题就是标准的模板题，只要一个Treap上去就AC了，所以没有什么价值，唯一的价值就是用来学习Treap前驱和后继函数在动态数据中的应用。
首先解释下题目意思：
输入n和m，你表示数轴的长度，当然这里的数轴是从1开始的正整数，m表示接下来有m个操作。
D x: The x-th village was destroyed.
就是摧毁数轴上的x值
Q x: The Army commands requested the number of villages that x-th
village was directly or indirectly connected with including itself.
询问x最左和最右没有被摧毁的两个数轴上点的距离.
R:
The village destroyed last was rebuilt.
重新修复最近一个被摧毁的点
Q x 的查询操作很容易让人想到平衡二叉树中的求前驱和后继函数，因此这题就解决了，
各种平衡二叉树均能推倒之，我是用Treap来写的。
具体的解法就是把D操作中的x insert到Treap中，R操作的时候就把最近的一次摧毁的点remove掉，
当然这里要另外开一个数组来记录所有被摧毁的点，便于查找最近被摧毁的点。
Q的时候就找前驱p和后继q,最后的答案就是q->key - p->key - 1;
这里开始的时候有个小技巧，就是把数轴的0点和n+1点也insert到Treap里面，
这样避免了求前驱和后继的时候返回的是null。
如果有不了解Treap（随机平衡二叉树）的可以见http://blog.csdn.net/acceptedxukai/article/details/6910685
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <queue>
using namespace std;
#define LL long long
const int N = 10005;
const int MAX = 1<<30;
class Treap
{
public :
struct Node
{
int key,cnt,fix;
Node *left,*right;
Node(int e) : key(e),cnt(1),fix(rand()) {}
}*root,*null;
Treap()
{
null = new Node(MAX);
null->cnt = 0;
root = null->right = null->left = null;
}
//右旋
void right_rat(Node *&x)
{
Node *y = x->left;
x->left = y->right;
y->right = x;
x = y;
}
//左旋
void left_rat(Node *&x)
{
Node *y = x->right;
x->right = y->left;
y->left = x;
x = y;
}
void insert(Node *&x,int e)
{
if(x == null)
{
x = new Node(e);
x->left = x->right = null;
}
else if(e < x->key)
{
insert(x->left,e);
if(x->left->fix < x->fix)right_rat(x);
}
else if(e > x->key)
{
insert(x->right,e);
if(x->right->fix < x->fix) left_rat(x);
}
else ++x->cnt;
}
//删除函数
void remove(Node *&x,int e)
{
if(x == null) return;
else if(e <x->key) remove(x->left,e);
else if(e > x->key) remove(x->right,e);
else if(--x->cnt <= 0)
{
if(x->left == null || x->right == null)
{
Node *y = x;
x = (x->left != null)? x->left : x->right;
delete y;
}
else
{
if(x->left->fix < x->right->fix)
{
right_rat(x);
remove(x->right,e);
}
else
{
left_rat(x);
remove(x->left,e);
}
}
}
}
//前驱
Node* Pred(Node* x,Node* y,int e)
{
if (x == null)
return y;
if (e < x->key)
return Pred(x->left,y,e);
return Pred(x->right,x,e);
}
//后继
Node *Succ(Node *x,Node *y,int e)
{
if(x == null) return y;
if(e <= x->key) return Succ(x->left,x,e);
return Succ(x->right,y,e);
}
int count(int e)
{
Node *p = Pred(root,null,e);//求前驱
Node *q = Succ(root,null,e);//求后继
return (q->key - p->key - 1) < 0 ? 0 : (q->key - p->key - 1);
}
};
int str[50005];
int main()
{
srand(time(0));
Treap tree;
int n,m,p,cnt=0;
tree.insert(tree.root,0);//插入0点
scanf("%d %d",&n,&m);
tree.insert(tree.root,n+1);//插入n+1点
for(int i = 0 ; i < m ; i ++)
{
char ch[3];
scanf("%s",ch);//用字符串输入比较方便，char太麻烦了
if(strcmp(ch,"D") == 0)
{
scanf("%d",&p);
str[cnt++]=p;
tree.insert(tree.root,p);
}
else if(strcmp(ch,"Q") == 0)
{
scanf("%d",&p);
printf("%d\n",tree.count(p));
}
else
{
p = str[cnt-1];
cnt--;
tree.remove(tree.root,p);
}
//getchar();
}
return 0;
}
