Lvat_s Blog

好多水题的题解忘了传……

直接Treap

#include<cstdio>
#include<cstdlib>
 
int n,mn,tag=0,root,leave=0,cnt;
char s[2];
 
struct Treap{
    int l,r,v,rnd,siz,w;
}tree[100005];
 
void Pre(){
tree[0].l=0;
tree[0].r=0;
root=0;
cnt=0;
srand(123465);
}
 
void Pushup(int rt){
tree[rt].siz=tree[tree[rt].l].siz+tree[tree[rt].r].siz+tree[rt].w;
}
 
void Lr(int &p){
int q=tree[p].r;
tree[p].r=tree[q].l;
tree[q].l=p;
tree[q].siz=tree[p].siz;
Pushup(p);
p=q;
}
 
void Rr(int &p){
int q=tree[p].l;
tree[p].l=tree[q].r;
tree[q].r=p;
tree[q].siz=tree[p].siz;
Pushup(p);
p=q;
}
 
void Ins(int &rt,int x){
if(!rt){
    rt=++cnt;
    tree[rt].l=0;
    tree[rt].r=0;
    tree[rt].v=x;
    tree[rt].siz=1;
    tree[rt].w=1;
    tree[rt].rnd=rand()<<15+rand();
    return;
}
tree[rt].siz++;
if(tree[rt].v>x){
    Ins(tree[rt].l,x);
    if(tree[tree[rt].l].rnd<tree[rt].rnd)Rr(rt);
    return;
}
else {
    Ins(tree[rt].r,x);
    if(tree[tree[rt].r].rnd<tree[rt].rnd)Lr(rt);
}
}
 
int Del(int &rt){
if(rt==0)return 0;
if(tree[rt].v+tag<0){
    int temp=tree[tree[rt].l].siz+1;
    rt=tree[rt].r;
    return temp+Del(rt);
}
int temp=Del(tree[rt].l);
tree[rt].siz-=temp;
return temp;
}
 
int Find(int rt,int x){
if(rt==0)return 0;
if(x<=tree[tree[rt].l].siz)return Find(tree[rt].l,x);
else {
    if(x>tree[tree[rt].l].siz+1)return Find(tree[rt].r,x-tree[tree[rt].l].siz-1);
    return tree[rt].v+tag;
}
}
 
int main(){
freopen("1503.in","r",stdin);
freopen("1503.out","w",stdout);
scanf("%d %d",&n,&mn);
for(int i=1;i<=n;i++){
    int Ts;
    scanf("%s %d",s,&Ts);
    if(s[0]=='I'){if(Ts>=mn){Ins(root,Ts-tag-mn);}}
    if(s[0]=='A'){tag+=Ts;}
    if(s[0]=='S'){tag-=Ts;leave+=Del(root);}
    if(s[0]=='F'){if(Ts>tree[root].siz)puts("-1");else printf("%d\n",Find(root,tree[root].siz-Ts+1)+mn);}
}
printf("%d\n",leave);
return 0;
}