平衡树例题

练习 #1 鬼子进村

题目背景

小卡正在新家的客厅中看电视。电视里正在播放放了千八百次依旧重播的《亮剑》，剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队，于是独立团与鬼子展开游击战。

题目描述

县城里有 \(n\) 个用地道相连的房子，第 \(i\) 个只与第 \(i-1\) 和第 \(i+1\) 个相连。这时有 \(m\) 个消息依次传来：

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

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

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

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

---

/*
Code by Ntsc_Hodaka
*/

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define pii pair<int,int>

///----///
#define rd read()
inline int read() {
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
inline void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}

///----///
const int N = 1e5 + 5;
const int M = 1e7 + 5;
const int INF = 1e9 + 5;
const double eps=1e-7;

struct node{
    int s[2],fa,v,cnt,size;
    //左右儿子,父亲,节点权值,值的数量,子树大小
    void init(int p1,int v1){
        fa=p1,v=v1;cnt=size=1;
    }
}tr[N];

bool f1;
///----///
int n,rt,idx;
int m,stk[N],top;
int vis[N];
///----///
bool f2;

void pushup(int x){//由左右儿子信息更新父亲的信息
    tr[x].size=tr[tr[x].s[0]].size+tr[tr[x].s[1]].size+tr[x].cnt;//儿子的size(子树和)加上自己的大小
    //size存的是以x为根节点的子树的信息
}


void rotate(int x){
    int y=tr[x].fa,z=tr[y].fa;
    int k=(tr[y].s[1]==x);//这里很重要!如果true,说明x为y的左儿子,应该继续左旋
    tr[y].s[k]=tr[x].s[k^1];//将y的左儿子设置为x的右儿子(1)
    tr[tr[x].s[k^1]].fa=y;
    tr[x].s[k^1]=y;//将x的右儿子设置为y(2)
    tr[y].fa=x;
    tr[z].s[(tr[z].s[1]==y)]=x;//自动判断原来的y是z的左/右儿子
    tr[x].fa=z;//更新z的儿子,x的新父亲(3)
    pushup(y);pushup(x);//别忘了修改信息
}

void splay(int x,int k){//将x旋转到k下方
    while(tr[x].fa!=k){
        int y=tr[x].fa,z=tr[y].fa;
        //第一次旋转,要分情况
        if(z!=k)//若z=k,说明只需要做单旋了(说明目标点就为x的父亲)
            if((tr[y].s[0]==x)^(tr[z].s[0]==y)){//若y为z左,x为y左或者y为z右,x为y右,异或和均为0,表示是直线型
                rotate(x);
            }else rotate(y);
        //第二次旋转,都是旋转x 
        rotate(x);
    }
    if(k==0)rt=x;//如果k=0说明x被旋转到了根节点
}


void find(int v){
    int x=rt;
    while(tr[x].s[v>tr[x].v]&&v!=tr[x].v){//如果:找到的点没有符合要求的儿子(即走到了最靠近v的点,但v是不存在的)或者找到了v
        x=tr[x].s[v>tr[x].v];//如果v>tr[x].v,那么就走右儿子
    }
    splay(x,0);//将v或者最靠近v的那个点旋转到根节点
}

int getlower(int v){
    find(v);
    int x=rt;//rt即v
    if(tr[x].v<v)return x;//若true,说明在find中就没有找到v,而是找到了最靠近v的点,若这个点的v<v,那么它就是v的前驱
    x=tr[x].s[0];//先走到v的左子树
    while(tr[x].s[1])x=tr[x].s[1];//然后不断走右儿子
    splay(x,0);
    return x;
}


int getbigger(int v){
    find(v);
    int x=rt;//rt即v
    if(tr[x].v>v)return x;//若true,说明在find中就没有找到v,而是找到了最靠近v的点,若这个点的v>v,那么它就是v的后继
    x=tr[x].s[1];//先走到v的右子树
    while(tr[x].s[0])x=tr[x].s[0];//然后不断走左儿子
    splay(x,0);
    return x;
}

void insert(int v){
     int x=rt,p=0;
     while(x&&tr[x].v!=v){
        p=x;x=tr[x].s[v>tr[x].v];//走到最靠近v的位置，如果v存在那么x停在v上，否则x走到满足v插入的位置的空节点
     }
     if(x)tr[x].cnt++;//x原来就存在了
     else{//添加一个节点
        x=++idx;
        if(p)tr[p].s[v>tr[p].v]=x;//p是x的父节点1
        tr[x].init(p,v);//初始化这个点，父亲为p，权值为v
     }
     splay(x,0);//splay防止退化成链
}

void del(int v){
    int pre=getlower(v),nxt=getbigger(v);
    splay(pre,0);splay(nxt,pre);//将pre旋转到根节点,将nxt旋转到pre的下方,只要就构造出了如图所示的图像
    int del=tr[nxt].s[0];
    if(tr[del].cnt>1)tr[del].cnt--,splay(del,0);//这里进行splay主要是为了pushup
    else tr[nxt].s[0]=0,splay(nxt,0);//直接清空nxt的左儿子,并且更新它
}


int getrank(int v){
    // find(v);
    // return tr[tr[rt].s[0]].size;//没有加上1的原因是树上还有一个无穷小的节点
    //不能用上面的代码！！会WA一个点
    insert(v);
    int res=tr[tr[rt].s[0]].size;
    del(v);
    return res;
}

int getval(int k){//查询第k小的点的权值
    int x=rt;
    k++;//因为有一个无穷小,所以实际上要查询的点是第k+1小的
    while(1){
        if(k<=tr[tr[x].s[0]].size)x=tr[x].s[0];//如果k<=左儿子的size,那么就走左儿子
        else if(tr[tr[x].s[0]].size+tr[x].cnt<k){//走右边
            k-=tr[tr[x].s[0]].size+tr[x].cnt;x=tr[x].s[1];//!!
        }else{
            // if(tr[y].size>=k)x=y;//走左边,若为true说明第k小的在左边,否则说明即不是右边,左边也没有,那就是它自己了
             break;
        }

    }
    splay(x,0);//splay仅仅是用来整理平衡树的,防止其退化为链
    return tr[x].v;
}



signed main() {
    // freopen("P5431_1.in", "r", stdin);
    // freopen("chfran.out", "w", stdout);
    cin>>n>>m;
    insert(0);insert(n+1);
    while(m--){
        char op;int x;
        cin>>op;
        if(op=='D'){
            cin>>x;
            stk[++top]=x;
            vis[stk[top]]=1;
            insert(x);
        }if(op=='R'){
            del(stk[top]);
            vis[stk[top--]]=0;
        }if(op=='Q'){
            cin>>x;
            if(vis[x])cout<<0<<endl;
            else cout<<tr[getbigger(x)].v-tr[getlower(x)].v-1<<endl;
//          cerr<<x<<" bg:"<<getbigger(x)<<" lo:"<<getlower(x)<<endl;
        }
    }


    return 0;
}

/*
不要把&&写成&啊！TT
*/