BZOJ 1503 splay

題意：維護一個序列的值，操作有插入一個值 删除一個值 全部值加上一個數 全部值減去一個數 詢問第k小是多少

解法：splay即可 把它當作普通的平衡樹就可以了 不要忘記操作完之後一定要splay哦

#include<cstdio>
#define maxn 222222
#define ls ch[rt][0]
#define rs ch[rt][1]
int scan()
{
    int res=0,ch;
    while(!((ch= getchar())>='0'&&ch<='9')){
        if(ch==EOF)return 1<<30;
    }
    res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        res=res*10+(ch-'0');
    return res;
}
int lim,sz[maxn],ch[maxn][2],fa[maxn];
int root,top;
int sum,cnt[maxn],val[maxn];
inline void up(int rt){sz[rt]=cnt[rt]+sz[ls]+sz[rs];}
inline void rot(int rt){
    int f=fa[rt],side=(ch[f][1]==rt),&ll=ch[rt][!side];
    fa[ll]=f,ch[f][side]=ll;
    fa[rt]=fa[f],ch[fa[f]][ch[fa[f]][1]==f]=rt;
    fa[f]=rt,ch[rt][!side]=f;
    up(f),up(rt);
}
inline void splay(int rt,int aim){
    while(fa[rt]!=aim){
        int f=fa[rt],ff=fa[f];
        if(ff==aim)rot(rt);
        else if((ch[f][1]==rt)==(ch[ff][1]==f))rot(f),rot(rt);
        else rot(rt),rot(rt);
    }if(!aim)root=rt;
}
inline void newnode(int &rt,int c){
    rt=++top;ls=rs=fa[rt]=0;
    sz[rt]=cnt[rt]=1;val[rt]=c;
}
inline void init(){
        sum=ch[0][0]=ch[0][1]=fa[0]=sz[0]=0;
        root=top=0; cnt[0]=0;
}
inline void ins(int &rt,int key,int f){
        if(!rt){
            newnode(rt,key);
            fa[rt]=f;
            splay(rt,0);
            return ;
        }
        if(key==val[rt]){
            cnt[rt]++;sz[rt]++;
            splay(rt,0);
            return ;
        }else if(key<val[rt]){
            ins(ls,key,rt);
        }else ins(rs,key,rt);
//        if(rt)up(rt);
}
inline void del(int &rt,int f){
        if(!rt) return ;
        if(val[rt]>=lim){
            del(ls,rt);
        }else{
             sum+=sz[ls]+cnt[rt];rt=rs;
             fa[rt]=f;
             if(!f)root=rt;
             del(rt,f);
        }
        if(rt)up(rt);
}
inline int findk(int rt,int k){
        if(k<sz[ls]+1){
            return findk(ls,k);
        }else if(k>(sz[ls]+cnt[rt])){
            return findk(rs,k-sz[ls]-cnt[rt]);
        }else{
            splay(rt,0);
            return val[rt];
        }
}
int main(){
    int n;
    char op[5];
    n=scan();lim=scan();
    int lim0=lim;
    init();
    while(n--){
        int k;
        scanf("%s",op);k=scan();
        if(op[0]=='I'){
            if(k<lim0){continue;}
            ins(root,k+lim-lim0,0);
        }else if(op[0]=='A'){
            lim-=k;
        }else if(op[0]=='S'){
            lim+=k;
            if(sz[root]>0)del(root,0);
        }else{
            int size=sz[root];
            if(k>size) printf("-1\n");
            else {
                printf("%d\n",findk(root,(size-k+1))-lim+lim0);
            }
        }
    }
    printf("%d\n",sum);
    return 0;
}