[题解]bzoj1503(NOI2004)郁闷的出纳员

OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。工资的频繁调整很让员工反感，尤其是集体扣除工资的时候，一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去，同样，每当公司招聘了一位新员工，我就得为他新建一个工资档案。老板经常到我这边来询问工资情况，他并不问具体某位员工的工资情况，而是问现在工资第k多的员工拿多少工资。每当这时，我就不得不对数万个员工进行一次漫长的排序，然后告诉他答案。好了，现在你已经对我的工作了解不少了。正如你猜的那样，我想请你编一个工资统计程序。怎么样，不是很困难吧？

输出文件的行数为F命令的条数加一。对于每条F命令，你的程序要输出一行，仅包含一个整数，为当前工资第k多的员工所拿的工资数，如果k大于目前员工的数目，则输出-1。输出文件的最后一行包含一个整数，为离开公司的员工的总数。

I命令的条数不超过100000 A命令和S命令的总条数不超过100 F命令的条数不超过100000 每次工资调整的调整量不超过1000 新员工的工资不超过100000

Solution

        这题可以用任意一种平衡树做，注意有相同工资的员工，插入的时候可以每个节点记录一个cnt表示有几个重复的员工。加减工资可以打标记（我就是这么写的），但由于都是统一加减，所以可以记录一个delta工资变化量，就可以不用打标记，但是要注意新插入的员工工资要减去delta来保证所有员工的变化量统一。删除的时候插入一个工资为最小工资的员工，把它旋转到根，删除右子树（为了方便统计第k大，我的平衡树是左子树>根>右子树，当然也可以反过来），记录下删了几个，再把额外插入的这个员工删掉。

       注意！注意！这题最坑的一点是统计走掉的员工数，但是如果是那种插入时就工资低于标准的那种，是不算在内的。这个坑了我一上午。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;inline int read(){int x=0,f=1;char ch=getchar();for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';return x*f;
}const int maxn=100010;
struct node{int fa,ch[2],size,data,add,cnt;
}T[maxn];
int n,minn,num=0,root=0,tot=0;void create(int x){T[++num].data=x;T[num].cnt=T[num].size=1;T[num].add=T[num].ch[0]=T[num].ch[1]=0;
}
void pushdown(int x){if(!T[x].add)return;if(T[x].ch[0]){T[T[x].ch[0]].data+=T[x].add;T[T[x].ch[0]].add+=T[x].add;}if(T[x].ch[1]){T[T[x].ch[1]].data+=T[x].add;T[T[x].ch[1]].add+=T[x].add;}T[x].add=0;
}
void update(int x){if(!x)return;T[x].size=T[x].cnt;if(T[x].ch[0])T[x].size+=T[T[x].ch[0]].size;if(T[x].ch[1])T[x].size+=T[T[x].ch[1]].size;
}
int getson(int x){return x==T[T[x].fa].ch[1];
}
void rotate(int p){if(!T[p].fa)return;int k=getson(p),fa=T[p].fa;int fafa=T[fa].fa;pushdown(fa);pushdown(p);T[fa].ch[k]=T[p].ch[k^1];if(T[p].ch[k^1])T[T[p].ch[k^1]].fa=fa;T[p].ch[k^1]=fa;T[fa].fa=p;T[p].fa=fafa;if(fafa)T[fafa].ch[fa==T[fafa].ch[1]]=p;update(fa);update(p);
}
void Splay(int u){for(int fa;(fa=T[u].fa);rotate(u)){if(T[fa].fa){rotate((getson(u)==getson(fa))?fa:u);}}root=u;
}
void Insert(int x){if(!root){create(x);root=num;T[root].fa=0;return;}int p=root,fa=0;while(p){pushdown(p);if(T[p].data==x){T[p].cnt++;update(p);update(fa);Splay(p);return;}fa=p;p=T[p].ch[x<T[p].data];}create(x);T[num].fa=fa;T[fa].ch[x<T[fa].data]=num;update(num);update(fa);Splay(num);
}
void fixup(){Insert(minn);tot+=T[T[root].ch[1]].size;T[root].ch[1]=0;if(T[root].cnt>1){T[root].cnt--;update(root);}else{root=T[root].ch[0];T[root].fa=0;}
}
void add(int x){T[root].add+=x;T[root].data+=x;
}
void sub(int x){T[root].add-=x;T[root].data-=x;fixup();
}
int find(int x){int p=root;while(1){pushdown(p);if(T[p].ch[0]&&x<=T[T[p].ch[0]].size)p=T[p].ch[0];else{int temp=T[T[p].ch[0]].size+T[p].cnt;if(x<=temp)return T[p].data;x-=temp;p=T[p].ch[1];}}
}
void Init(){n=read();minn=read();root=0;
}
void Work(){char opt;int k;while(n--){opt=getchar();while(opt==' '||opt=='\n')opt=getchar();k=read();if(opt=='I'){if(k>=minn)Insert(k);}else if(opt=='A')add(k);else if(opt=='S')sub(k);else{if(k>T[root].size)printf("-1\n");else printf("%d\n",find(k));}}printf("%d\n",tot);
}int main(){Init();Work();return 0;
}