P1486

Sun_Email · 2023-05-14 08:45:27 · 个人记录

显然是一道平衡树的题，在这里我用的是 Splay。A 和 S 操作用一个全局变量维护的一些注意事项（在这里我用的变量名是 all）其他题解里讲的很清楚，我也不多说了。

不过题目中说 F 操作需要查询的是第 k 大的值，而普通的 Splay 都是左小右大的，只能查询到第 k 小的值。怎么办呢？

考虑把所有工资乘上 -1，这样就可以查到第 k 大的值了。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
int n,minn,all=0,sum=0,t1,yy[1000001],c=0,ae=0;
int rt,tot=0,sz[100001],fa[100001],val[100001],cnt[100001],ch[100001][2];
char op[2];
inline bool get(int x){
    return ch[fa[x]][1]==x;
}
inline void push_up(int x){
    if(!x){
        return;
    }
    sz[x]=cnt[x];
    if(ch[x][0]){
        sz[x]+=sz[ch[x][0]];
    }
    if(ch[x][1]){
        sz[x]+=sz[ch[x][1]];
    }
}
void rotate(int x){
    int y=fa[x],z=fa[y],k=get(x);
    ch[y][k]=ch[x][k^1];fa[ch[x][k^1]]=y;
    ch[x][k^1]=y;fa[y]=x;fa[x]=z;
    if(z){
        ch[z][ch[z][1]==y]=x;
    }
    push_up(y);push_up(x);
}
void splay(int x,int g=0){
    while(fa[x]!=g){
        int y=fa[x],z=fa[y];
        if(z){
            rotate(get(x)==get(y)?y:x);
        }
        rotate(x);
    }
    if(!g){
        rt=x;
    }
}
void find(int x){
    int u=rt;
    if(!u){
        return;
    }
    while(ch[u][val[u]<x]&&val[u]!=x){
        u=ch[u][val[u]<x];
    }
    splay(u,0);
}
int query_kth(int x){
    int u=rt;
    while(1){
        if(ch[u][0]&&sz[ch[u][0]]>=x){
            u=ch[u][0];
        }
        else{
            int tmp=sz[ch[u][0]]+cnt[u];
            if(tmp>=x){
                return val[u];
            }
            u=ch[u][1];x-=tmp;
        }
    }
}
void insert(int x){
    int u=rt,f=0;
    while(u&&val[u]!=x){
        f=u;u=ch[u][val[u]<x];
    }
    if(u){
        ++cnt[u];push_up(u);push_up(f);
    }
    else{
        u=++tot;sz[u]=cnt[u]=1;val[u]=x;fa[u]=f;
        if(f){
            ch[f][val[f]<x]=u;push_up(f);
        }
        else{
            rt=u;
        }
    }
    splay(u,0);
}
int pre(int x){
    find(x);
    if(val[rt]<x){
        return rt;
    }
    int u=ch[rt][0];
    while(ch[u][1]){
        u=ch[u][1];
    }
    return u;
}
void del(int x){
    find(x);
    if(cnt[rt]>1){
        --cnt[rt];push_up(rt);return;
    }
    if(!ch[rt][0]&&!ch[rt][1]){
        rt=0;return;
    }
    if(!ch[rt][0]||!ch[rt][1]){
        rt=ch[rt][0]+ch[rt][1];
        fa[rt]=0;return;
    }
    int ort=rt,lb=pre(x);
    splay(lb,0);
    ch[rt][1]=ch[ort][1];fa[ch[ort][1]]=rt;
    push_up(rt);
}
void check(){
    for(int i=1;i<=c;++i){
        if(yy[i]==-0x3f3f3f3f){
            continue;
        }
        if(yy[i]+all<minn){
            del(-yy[i]);yy[i]=-0x3f3f3f3f;++sum;
        }
    }
}
int main(){
    int cnt=0;
    scanf("%d%d",&n,&minn);
    for(int i=1;i<=n;++i){
        scanf("%s%d",op,&t1);
        if(op[0]=='I'){
            if(t1<minn){
                continue;
            }
            ++ae;yy[++c]=t1-all;
            insert(-t1+all);
        }
        else if(op[0]=='A'){
            all+=t1;
        }
        else if(op[0]=='S'){
            all-=t1;
            check();
        }
        else if(op[0]=='F'){
            if(ae-sum<t1){
                printf("-1\n");continue;
            }
            printf("%d\n",-query_kth(t1)+all);
        }
    }
    printf("%d",sum);
    return 0;
}

完结撒花