P1486 [NOI2004]郁闷的出纳员

刺骨的言语ヽ痛彻心扉 2023-06-04 08:00 87阅读 0赞

[**题目链接**][Link 1]

**这道题需要动态插入，删除，求排名，看到这就想到了平衡树。由于本人只会splay，所以就用splay来做这道题，这道题插入和删除都是模板，但是题中还有一个比价坑的地方就是工资的调整。但我做不到在平衡树上修改点权。如果每一个都去插入和删除的复杂度显然非常高。看了题解发现，可以维护一个变量来记录每次工资调整时的值delta，像这样的话我们插入的k值就应该是k-delta，为什么要这样做呢，因为我们显然无法修改之前的点权，这样一来就是维护一个相对的大小。**

**重点还有如何把工资低于下界的人都删去。我们在操作之前提前插入两个哨兵节点+/-inf，这样可以避免操作时的错误，这是一个技巧，需要记住。在删除的时候把权值为-inf的点旋转到根节点，然后将全值为下界的点转到根节点的右儿子上，这是根节点右儿子的左儿子就是比工资下界小的所有节点，然后直接删除即可。**

**注意再求排名的时候要减去两个插入的哨兵节点。**

**代码如下：**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+7;
    const int inf=0x7fffffff;
    int n,minn;
    char opt[maxn];
    int key[maxn],fa[maxn],cnt[maxn],size[maxn],ch[maxn][2];
    int rt,sz;
    int k;
    int tot;
    int delta;
    void pushup(int x){
        size[x]=size[ch[x][0]]+size[ch[x][1]]+cnt[x];
    }
    bool check(int x){
        return ch[fa[x]][1]==x;
    }
    void clear(int x){
        fa[x]=cnt[x]=size[x]=ch[x][1]=ch[x][0]=key[x]=0;
    }
    void rotate(int x){
        int y=fa[x],z=fa[y],who=check(x);
        ch[y][who]=ch[x][who^1];
        fa[ch[y][who]]=y;
        ch[x][who^1]=y;
        fa[y]=x,fa[x]=z;
        if(z) ch[z][ch[z][1]==y]=x;
        pushup(y);pushup(x);
    }
    void splay(int x,int goal){
        for(int f;(f=fa[x])!=goal;rotate(x)){
            if(fa[f]!=goal) rotate((check(f)==check(x))?f:x);
        }
        if(!goal) rt=x;
    }
    void insert(int x){
        if(!rt){
            rt=++sz;
            key[sz]=x;
            size[sz]=1;
            cnt[sz]=1;
            return;
        }
        int now=rt,f=0;
        while(1){
            if(key[now]==x){
                cnt[now]++;
                pushup(f);
                pushup(now);
                splay(now,0);
                return;
            }
            f=now,now=ch[now][key[now]<x];
            if(!now){
                sz++;
                size[sz]=cnt[sz]=1;
                fa[sz]=f;
                ch[f][key[f]<x]=sz;
                key[sz]=x;
                pushup(f);
                splay(sz,0);
                return;
            } 
        }
    }
    int nxt(){
        int now=ch[rt][1];
        while(ch[now][0]) now=ch[now][0];
        return now;
    }
    int pre(){
        int now=ch[rt][0];
        while(ch[now][1]) now=ch[now][1];
        return now;
    }
    int id(int x){
        int now=rt;
        while(1){
            if(x==key[now]) return now;
            else{
                if(x<key[now]) now=ch[now][0];
                else now=ch[now][1];
            }
        }
    }
    int rank(int x){
        int now=rt,ans=0;
        while(1){
            if(x<key[now]) now=ch[now][0];
            else{
                ans+=size[ch[now][0]];
                if(x==key[now]){
                    splay(now,0);
                    return ans+1;
                }
                ans+=cnt[now];
                now=ch[now][1];
            }
        }
    }
    void del(int x){
        rank(x);
        if(cnt[rt]>1){
            cnt[rt]--;
            pushup(rt);
            return;
        }
        if(!ch[rt][1]&&!ch[rt][0]){
            clear(rt);
            rt=0;
            return;
        }
        if(!ch[rt][1]){
            int oldroot=rt;
            rt=ch[rt][0];
            fa[rt]=0;
            clear(oldroot);
            return;
        }
        else if(!ch[rt][0]){
            int oldroot=rt;
            rt=ch[rt][1];
            fa[rt]=0;
            clear(oldroot);
            return;
        }
        int oldroot=rt,left=pre();
        splay(left,0);
        fa[ch[oldroot][1]]=rt;
        ch[rt][1]=ch[oldroot][1];
        clear(oldroot);
        pushup(rt);
    }
    int val(int x){
        int now=rt;
        while(1){
            if(ch[now][0]&&x<=size[ch[now][0]]) now=ch[now][0];
            else{
                int tmp=size[ch[now][0]]+cnt[now];
                if(x<=tmp) return key[now];
                x-=tmp;
                now=ch[now][1];
            }
        }
    }
    int main(){
        scanf("%d%d",&n,&minn);
        insert(inf);
        insert(-inf);
        for(int i=1;i<=n;i++){
            scanf("%s",opt);
            if(opt[0]=='I'){
                scanf("%d",&k);
                if(k<minn) continue;
                insert(k-delta);
                tot++;
            }
            if(opt[0]=='A'){
                scanf("%d",&k);
                delta+=k;
            }
            if(opt[0]=='S'){
                scanf("%d",&k);
                delta-=k;
                insert(minn-delta);
                int a=id(minn-delta);
                int b=id(-inf);
                splay(b,0);
                splay(a,b);
                ch[ch[rt][1]][0]=0;
                del(minn-delta);
            }
            if(opt[0]=='F'){
                scanf("%d",&k);
                int kkksc03=rank(inf)-2;
                if(kkksc03<k){
                    printf("-1\n");
                    continue;
                }
                int ans=val(kkksc03+2-k);
                printf("%d\n",ans+delta);
            }
        }
        int kkksc03=rank(inf)-2;
        int ans=tot-kkksc03;
        printf("%d\n",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/LJB666/p/11559826.html

[Link 1]: https://www.luogu.org/problem/P1486
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/83c15e9b12e04fbdbc7d133f2e67a55b.png