NOI2004郁闷的出纳员
输入描述 Input Description
第一行有两个非负整数n和min。n表示下面有多少条命令，min表示工资下界。
接下来的n行，每行表示一条命令。命令可以是以下四种之一：
名称 格式 作用 I命令 I_k 新建一个工资档案，初始工资为k。如果某员工的初始工资低于工资下界，他将立刻离开公司。 A命令 A_k 把每位员工的工资加上k S命令 S_k 把每位员工的工资扣除k F命令 F_k 查询第k多的工资 _（下划线）表示一个空格，I命令、A命令、S命令中的k是一个非负整数，F命令中的k是一个正整数。
在初始时，可以认为公司里一个员工也没有。
输出描述 Output Description
输出文件的行数为F命令的条数加一。
对于每条F命令，你的程序要输出一行，仅包含一个整数，为当前工资第k多的员工所拿的工资数，如果k大于目前员工的数目，则输出-1。
输出文件的最后一行包含一个整数，为离开公司的员工的总数。
样例输入 Sample Input
9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2
样例输出 Sample Output
10
20
-1
2
题解：模板题吧，就是记录一个变化量搞一搞，裸的Treap，记录重复哪里搞错了，调了一个小时，无语了。
1 #include<cstring> 2 #include<cmath> 3 #include<iostream> 4 #include<algorithm> 5 #include<cstdio> 6 7 #define ls tr[p].l 8 #define rs tr[p].r 9 #define N 100007 10 using namespace std; 11 inline int read() 12 { 13 int x=0,f=1;char ch=getchar(); 14 while(ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();} 15 while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} 16 return x*f; 17 } 18 19 int n,m,sz,rt,ans,bh; 20 char flag[3]; 21 struct Node 22 { 23 int l,r,val,siz,rnd,ct;//记录左儿子，右儿子，点值，该子树大小，随机的值，该点值出现的次数。 24 }tr[N];//最多多少个节点，就开多少空间 25 26 inline int rand(){ 27 static int seed = 2333; 28 return seed = (int)((((seed ^ 998244353) + 19260817ll) * 19890604ll) % 1000000007); 29 } 30 inline void update(int p) 31 { 32 tr[p].siz=tr[ls].siz+tr[rs].siz+tr[p].ct; 33 } 34 void lturn(int &p) 35 { 36 int t=tr[p].r;tr[p].r=tr[t].l;tr[t].l=p; 37 tr[t].siz=tr[p].siz;update(p);p=t; 38 } 39 void rturn(int &p) 40 { 41 int t=tr[p].l;tr[p].l=tr[t].r;tr[t].r=p; 42 tr[t].siz=tr[p].siz;update(p);p=t; 43 } 44 void ins(int &p,int x) 45 { 46 if (p==0) 47 { 48 p=++sz; 49 tr[p].siz=tr[p].ct=1,tr[p].val=x,tr[p].rnd=rand(); 50 return; 51 } 52 tr[p].siz++; 53 if (tr[p].val==x) tr[p].ct++; 54 else if (x>tr[p].val) 55 { 56 ins(tr[p].r,x); 57 if (tr[rs].rnd<tr[p].rnd) lturn(p); 58 }else 59 { 60 ins(tr[p].l,x); 61 if (tr[ls].rnd<tr[p].rnd) rturn(p); 62 } 63 } 64 int del(int &p,int x) 65 { 66 if (p==0) return 0; 67 if (tr[p].val<x) 68 { 69 int t=tr[ls].siz+tr[p].ct;p=rs; 70 return t+del(p,x); 71 } 72 else 73 { 74 int t=del(ls,x);tr[p].siz-=t; 75 return t; 76 } 77 } 78 int find_sz(int p,int x) 79 { 80 if (p==0) return 0; 81 if (x<=tr[ls].siz) return find_sz(ls,x); 82 x-=tr[ls].siz; 83 if (x<=tr[p].ct) return tr[p].val+bh; 84 x-=tr[p].ct; 85 return find_sz(rs,x); 86 } 87 int main() 88 { 89 n=read(),m=read(); 90 for (int i=1;i<=n;i++) 91 { 92 scanf("%s",flag);int x=read(); 93 if (flag[0]=='I'&&x>=m) ins(rt,x-bh); 94 if (flag[0]=='A') bh+=x; 95 if (flag[0]=='S') 96 { 97 bh-=x; 98 ans+=del(rt,m-bh); 99 } 100 if (flag[0]=='F') printf("%d ",(x>tr[rt].siz)?-1:find_sz(rt,tr[rt].siz-x+1)); 101 } 102 printf("%d",ans); 103 }