学步园

这种题就是标准的模板题，只要一个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;
}