题解 P1486 【[NOI2004]郁闷的出纳员】

**对我来说，这大概是一题$treap$模板** **人话题意：** 给出两个整数：$n$和$min$ 你需要写一种数据结构，并维护以下$n$个操作$(k$已给出$)$： $(I$命令$)1.$输入$k,$ 若$k>=min,$ 则插入$k.$ $(A$命令$)2.$将每个数加上$k.$ $(S$命令$)3.$将每个数减去$k,$并删除所有$<min$的数$.$ $(F$命令$)4.$查询第$k$大的数$($注意不是第$k$小$)$ 最后输出有几个数被删除了$($要加上$I$命令中没有插入的数$)$ 很显然，这些操作都是$treap$可以维护的$,$ 接下来我们逐个操作来分析$:$ 首先，我们建立一个$sum$变量来统计数字的加减幅度，作用见下$.$ $I$命令$:$常规$insert$操作 $A$命令$:$将$min$减去$k,$ 将$sum$加上$k,$ 因为每个数都加$k$，而我们通过每个数要求的是第$k$大 （不影响）以及是否$<min,$ 所以如此操作 $S$命令$:$将$min$加上$k,$ 将$sum$减去$k($理由与$A$命令相同$),$ 然后进行一遍$while$循环$,$ 只 要当前有小于$min$的数字，就删掉$(pre$和$delete$操作$)$ $ps: pre$ 操作要考虑等于$min$的数也要删除的情况 $F$命令$:$常规$find-rank$操作 上代码之前几点提醒$:$ $1.$ 最后一行输出跳槽的人的个数而不是剩下人的个数 $2.$ 有人初始工资相同，所以要改动$pre$函数 $3. F$ 操作是求第$k$大的数不是第$k$小 代码$:$ ``` #include <cstdlib> #include <iostream> using namespace std; int n,minn,x,tot,root,INF=0x7fffffff,num,sum,s; //n,minn为输入，opt为操作种类，x=题面中的k //tot为插入中用到的,root=树根(-INF) //s=进入公司的总人数,num=最后留在公司的人数 char opt; struct treap { int l,r,cnt,siz,val,dat; }a[100001]; void update(int p) { a[p].siz=a[p].cnt+a[a[p].l].siz+a[a[p].r].siz; } int New(int val) { a[++tot].val=val; a[tot].dat=rand(); a[tot].cnt=a[tot].siz=1; return tot; } void build() { New(-INF);New(INF); root=1;a[1].r=2; update(root); } void zig(int &p) { int q=a[p].l; a[p].l=a[q].r; a[q].r=p;p=q; update(a[p].r);update(p); }//right rotate void zag(int &p) { int q=a[p].r; a[p].r=a[q].l; a[q].l=p;p=q; update(a[p].l);update(p); }//left rotate void ins(int &p,int val) { if(p==0) { p=New(val); update(p); return; } if(val==a[p].val) { a[p].cnt++; update(p); return; } if(val<a[p].val) { ins(a[p].l,val); if(a[p].dat<a[a[p].l].dat)zig(p);//right rotate } if(val>a[p].val) { ins(a[p].r,val); if(a[p].dat<a[a[p].r].dat)zag(p);//left rotate } update(p); }//插入操作 void del(int &p,int val) { if(p==0)return; if(a[p].val==val) { if(a[p].cnt>1){a[p].cnt--;update(p);return;} if(a[p].l!=0||a[p].r!=0) { if(a[p].r==0||a[a[p].l].dat>a[a[p].r].dat){zig(p);del(a[p].r,val);} else{zag(p);del(a[p].l,val);} update(p); } else p=0; return; } if(val<a[p].val)del(a[p].l,val); else del(a[p].r,val); update(p); }//删除操作 int find_rank(int p,int val) { if(p==0)return -1; if(a[a[p].l].siz>=val)return find_rank(a[p].l,val); if(a[a[p].l].siz+a[p].cnt>=val)return a[p].val; return find_rank(a[p].r,val-a[p].cnt-a[a[p].l].siz); }//查找操作 int pre(int val) { int p=root,ans=1; while(p!=0) { if(a[p].val==val) { ans=p; break; } if(a[p].val<val&&a[p].val>a[ans].val)ans=p; if(a[p].val<val)p=a[p].r; else p=a[p].l; } return a[ans].val; }//求前驱 int main() { cin>>n>>minn;build(); for(int i=1;i<=n;i++) { cin>>opt>>x; if(opt=='I')if(x-sum>=minn)ins(root,x-sum),num++,s++; if(opt=='F') { if(num<x)cout<<-1<<endl; else cout<<find_rank(root,num-x+2)+sum<<endl; } if(opt=='A')minn-=x,sum+=x; if(opt=='S') { minn+=x;sum-=x; int a1=minn-1,a2; while(pre(a1)!=-INF) { a2=a1;a1=pre(a1); del(root,pre(a2)); num--; } } } cout<<s-num<<endl; } ```