P1503 鬼子进村（Treap树）

题意：

县城里有 nn 个用地道相连的房子，第 ii 个只与第 i-1i−1 和第 i+1i+1 个相连。这时有 mm 个消息依次传来：

1. 若消息为 D x：鬼子将 xx 号房子摧毁了，地道被堵上。

2. 若消息为 R ：村民们将鬼子上一个摧毁的房子修复了。

3. 若消息为 Q x：有一名士兵被围堵在 xx 号房子中。

李云龙收到信息很紧张，他想知道每一个被围堵的士兵能够到达的房子有几个。

题解：

对每个D操作和R操作，就是在平衡树上做插入和删除，对Q操作就是在平衡树上查询前驱和后继，做差就是答案。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
const int inf=1e9;
int n,m;
int a[maxn];
struct Treap_tree {
    int ch[2];
    int v;
    int dat;//优先级 
    int size;//子树节点数 
    int cnt;//重复数 
}t[maxn];
int tot;
int root;
int newNode (int v) {
    tot++;
    t[tot].v=v;
    t[tot].dat=rand();//随机优先级
    t[tot].size=1;
    t[tot].cnt=1;
    return tot; 
} 
void pushup (int x) {
    t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+t[x].cnt;
}
void build () {
    
}
void rotate (int &id,int d) {
    int tt=t[id].ch[d^1];
    t[id].ch[d^1]=t[tt].ch[d];
    t[tt].ch[d]=id;
    id=tt;
    pushup(t[id].ch[d]);
    pushup(id);
}
void ins (int &id,int v) {
    if (!id) {
        id=newNode(v);
        return;
    }
    if (v==t[id].v) t[id].cnt++;
    else {
        ins(t[id].ch[v>t[id].v],v);
        if (t[id].dat<t[t[id].ch[v>t[id].v]].dat) rotate(id,v<t[id].v);
    }
    pushup(id);
}
void remove (int &id,int v) {
    if (!id) return;
    if (v==t[id].v) {
        if (t[id].cnt>1) {
            t[id].cnt--;
            pushup(id);
            return;
        }
        if (t[id].ch[0]||t[id].ch[1]) {
            if (!t[id].ch[1]||t[t[id].ch[0]].dat>t[t[id].ch[1]].dat) {
                rotate(id,1);
                remove(t[id].ch[1],v);
            }
            else {
                rotate(id,0);
                remove(t[id].ch[0],v);
            }
            pushup(id);
        }
        else
            id=0;
        return;
    }
    remove(t[id].ch[v>t[id].v],v);
    pushup(id);
}
int rk (int id,int v) {
    if (!id) return 0;
    if (v==t[id].v) 
        return t[t[id].ch[0]].size+1;
    else if (v<t[id].v)
        return rk(t[id].ch[0],v);
    else
        return t[t[id].ch[0]].size+t[id].cnt+rk(t[id].ch[1],v);
}
int kth (int id,int k) {
    if (!id) return inf;
    if (k<=t[t[id].ch[0]].size)
        return kth(t[id].ch[0],k);
    else if (k<=t[t[id].ch[0]].size+t[id].cnt)
        return t[id].v;
    else
        return kth(t[id].ch[1],k-t[t[id].ch[0]].size-t[id].cnt);
}
int get_pre (int id,int v) {
    int pre;
    while (id) {
        if (t[id].v<v)
            pre=t[id].v,id=t[id].ch[1];
        else
            id=t[id].ch[0];
    }
    return pre;
}
int get_next (int id,int v) {
    int nxt;
    while (id) {
        if (t[id].v>v)
            nxt=t[id].v,id=t[id].ch[0];
        else
            id=t[id].ch[1];
    }
    return nxt;
}


int main () {
    scanf("%d%d",&n,&m);
    vector<int> ans;
    stack<int> pre;
    ins(root,0);
    ins(root,n+1);
    for (int i=1;i<=m;i++) {
        string s;
        int x;
        cin>>s;
        if (s=="D")  
            scanf("%d",&x),a[x]=1,ins(root,x),pre.push(x);
        if (s=="R")
            a[pre.top()]=0,remove(root,pre.top()),pre.pop();
        if (s=="Q") {
            scanf("%d",&x);
            if (a[x]==1) {
                ans.push_back(0);
                continue;
            }
            int l=get_pre(root,x);
            int r=get_next(root,x);
            ans.push_back(r-l-1);
        }
    }
    for (int i=0;i<ans.size();i++) printf("%d
",ans[i]);
}