P1486 [NOI2004]郁闷的出纳员

· · 个人记录

这个题算是平衡树系列的一个进阶版本了吧qwq.

好吧我承认，这个题我一开始做的时候已经想出了大约60%的样子，但是最后还是偷偷地瞅了眼题解，发现似乎很有道理，然后A了emmmm.

那么好像很显然，我们坑定不能一个一个地修改，区间修改由于每次都是1~n，所以并没有什么很大的意义。所以我们可以考虑引入一个标记，每次A就delta+=num每次I就insert(num-delta)，询问时就cout<<query+delta,再加上几个判断是不是非法操作。

那么，在这里我们考虑将$-INF$和$INF$在一开始就插入平衡树里。每次$insert$操作$tot++$,最后只需要用$$tot-(find\_rank(INF)-2)$$就可以算出离职人数。 那么只剩下最后一个问题了——我们该怎么删除呢？这里就需要用到一个二叉搜索树里很精妙的操作了——删除根的子树。我们可以在执行$S$操作时先$delta-=num$，然后将$-INF$旋转到根节点，将$minn-delta$旋转到根节点的右儿子，然后删除根节点的右子树的左子树即可。 诶这个操作很熟悉啊，不也是区间翻转时的操作吗？ 诶怎么旋转$minn-delta$啊？ 我们可以很简单地插入删除，这很简单，但是为什么要以$minn-delta$作为所删除的单调区间的上界？这个地方你可以稍微意会一下……**因为我们插入的是$num-delta$啊!** 嗯，我还是太弱了。 # $\color{red}Code: 
#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 1000000
#define INF 283653129 
int f[MAXN],cnt[MAXN],value[MAXN],sons[MAXN][2],sub_size[MAXN],whole_size,root;                 
inline int qread(){
    int res=0,k=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')k=-1;
        c=getchar();
    }
    while(isdigit(c)){
        res=(res<<1)+(res<<3)+c-48;
        c=getchar();
    }
    return res*k;
}
inline void S_Clear(int x){
    sons[x][0]=sons[x][1]=f[x]=sub_size[x]=cnt[x]=value[x]=0; 
}
inline bool get_which(int x){
    return sons[f[x]][1]==x;
}
inline void update(int x){
    if (x){  
        sub_size[x]=cnt[x];  
        if (sons[x][0]) sub_size[x]+=sub_size[sons[x][0]];  
        if (sons[x][1]) sub_size[x]+=sub_size[sons[x][1]];  
    }  
    return ;
}
inline void rotate(int x){
    int father=f[x],g_father=f[father],which_son=get_which(x);
    sons[father][which_son]=sons[x][which_son^1];
    f[sons[father][which_son]]=father;
    sons[x][which_son^1]=father;
    f[father]=x;
    f[x]=g_father;
    if(g_father){
        sons[g_father][sons[g_father][1]==father]=x;
    }
    update(father);
    update(x);
}
inline void splay(int x,int goal){
    for(int qwq;(qwq=f[x])!=goal;rotate(x)){
        if(f[qwq]!=goal){
            rotate(get_which(x)==get_which(qwq)?qwq:x);
        }
    } 
    if(!goal){
        root=x;
    }
}
inline void insert(int x){
    if(!root){
        whole_size++;
        sons[whole_size][0]=sons[whole_size][1]=f[whole_size]=0;
        root=whole_size;
        sub_size[whole_size]=cnt[whole_size]++;
        value[whole_size]=x;
        return ;
    } 
    int now=root,fa=0;
    while(1){
        if(x==value[now]){
            cnt[now]++;
            update(now);
            update(fa);
            splay(now,0);
            break;
        }
        fa=now;
        now=sons[now][value[now]<x];
        if(!now){
            whole_size++;
            sons[whole_size][0]=sons[whole_size][1]=0;
            f[whole_size]=fa;
            sub_size[whole_size]=cnt[whole_size]=1;
            sons[fa][value[fa]<x]=whole_size;
            value[whole_size]=x;
            update(fa);
            splay(whole_size,0);
            break; 
        }
    }

}
inline int find_num(int x){ 
    int now=root;
    while(1){
        if(sons[now][0]&&x<=sub_size[sons[now][0]])
        now=sons[now][0];
        else {
            int temp=(sons[now][0]?sub_size[sons[now][0]]:0)+cnt[now];
            if(x<=temp)return value[now];
            x-=temp;
            now=sons[now][1];
        }
    }
}
inline int find_ID(int x){
    int now=root;
    while(1){
        if(x==value[now]){
            return now;
        }
        else now=sons[now][value[now]<x]; 
    }
}
inline int find_rank(int x){
      int now=root,ans=0;  
    while(1){  
        if (x<value[now])  
          now=sons[now][0];  
        else{  
            ans+=(sons[now][0]?sub_size[sons[now][0]]:0);  
            if (x==value[now]){  
                splay(now,0); return ans+1;  
            }  
            ans+=cnt[now];  
            now=sons[now][1];  
        }  
    }  
}
inline int find_pre(){
    int now=sons[root][0];
    while(sons[now][1])now=sons[now][1];
    return now;
}
inline int find_suffix(){
    int now=sons[root][1];
    while(sons[now][0])now=sons[now][0];
    return now;
}
inline void my_delete(int x){
    int hhh=find_rank(x);
    if (cnt[root]>1){
    cnt[root]--; 
    update(root); 
    return;
    }  
    if (!sons[root][0]&&!sons[root][1]) {
    S_Clear(root);
    root=0;
    return;
    }  
    if (!sons[root][0]){  
        int old_root=root; 
        root=sons[root][1];
        f[root]=0; 
        S_Clear(old_root); 
        return;  
    }  

    else if (!sons[root][1]){  
        int old_root=root; 
        root=sons[root][0]; 
        f[root]=0; 
        S_Clear(old_root); 
        return;  
    } 
    int left_max=find_pre(),old_root=root;  
    splay(left_max,0);  
    sons[root][1]=sons[old_root][1];  
    f[sons[old_root][1]]=root;  
    S_Clear(old_root);  
    update(root);  
}
int main(){
    int m,num,minn;
    char a;
    cin>>m>>minn;
    insert(-INF);
    insert(INF); 
    int delta=0,sumtot=0;
    for(int i=1;i<=m;i++){
        cin>>a>>num;
        switch(a){
            case 'I' :{
                if(num<minn)break;
                insert(num-delta);
                sumtot++;
                break;
            } 
            case 'A':{
                delta+=num;
                break;
            }
            case 'S':{
                delta-=num;
                insert(minn-delta);
                int a=find_ID(-INF),b=find_ID(minn-delta);
                splay(a,0);
                splay(b,a);
                sons[sons[root][1]][0]=0; 
                my_delete(minn-delta);
                break;
            }
            case 'F':{
                int sumnow=find_rank(INF)-2;
                if(sumnow<num){
                cout<<-1<<endl; 
                break;
                }
                int  res=find_num(sumnow+2-num);
                cout<<res+delta<<endl;
                break;
            }
        }
    }
    int sumnow=find_rank(INF)-2;  
    cout<<sumtot-sumnow;
    return 0;
}

代码好长啊……足足写了5.04K