Description
OIER公司是一家大型专业化软件公司,有着数以万计的员 工。作为一名出纳员,我的任务之一便是统计每位员工的工资。这本来是一份不错的工作,但是令人郁闷的是,我们的老板反复无常,经常调整员工的工资。如果他 心情好,就可能把每位员工的工资加上一个相同的量。反之,如果心情不好,就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。 工资的频繁调整很让员工反感,尤其是集体扣除工资的时候,一旦某位员工发现自己的工资已经低于了合同规定的工资下界,他就会立刻气愤地离开公司,并且再也 不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司,我就要从电脑中把他的工资档案删去,同样,每当公司招聘了一位新员工,我就得为他新 建一个工资档案。老板经常到我这边来询问工资情况,他并不问具体某位员工的工资情况,而是问现在工资第k多的员工拿多少工资。每当这时,我就不得不对数万 个员工进行一次漫长的排序,然后告诉他答案。好了,现在你已经对我的工作了解不少了。正如你猜的那样,我想请你编一个工资统计程序。怎么样,不是很困难 吧?
splay维护工资的顺序;
定义一个change变量,全体修改的操作就修改change,每次询问工资用splay的返回值加上change的值;
不要问我为啥会有个堆。。。。我是脑残
/************************************************************** Problem: 1503 User: 1115825064 Language: C++ Result: Accepted Time:868 ms Memory:5296 kb ****************************************************************/ #include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,jx,change,leave=0; const int N=100010; struct T{ int lc,rc,fa,size,w; }tr[N]; int tott,totd; struct D{ int pr,w; }dui[N]; int root=0; void up(int i) { if(i==1) return ; if(dui[i].w<dui[i>>1].w) { swap(dui[i],dui[i>>1]); up(i>>1); } } void put(int pr,int w) { dui[++totd].pr=pr; dui[totd].w=w; up(totd); } void down(int i) { if(i<<1>totd) return ; int a=i<<1; if(a+1<=totd&&dui[a+1].w<dui[a].w) a++; if(dui[i].w>dui[a].w) { swap(dui[i],dui[a]); down(a); } } void pop() { dui[1]=dui[totd--]; down(1); } void setup(int i) { if(!i) return ; tr[i].size=tr[tr[i].lc].size+tr[tr[i].rc].size+1; } void jia(int i,int k) { if(k>tr[i].w) { if(tr[i].rc) { jia(tr[i].rc,k); setup(i); } else { tr[i].rc=++tott; tr[tott].fa=i; tr[tott].w=k; tr[tott].size=1; tr[tott].rc=0; tr[tott].lc=0; setup(i); } } else { if(tr[i].lc) { jia(tr[i].lc,k); setup(i); } else { tr[i].lc=++tott; tr[tott].fa=i; tr[tott].w=k; tr[tott].size=1; tr[tott].rc=0; tr[tott].lc=0; setup(i); } } } void xuan(int x) { int y=tr[x].fa,z=tr[y].fa; if(x==tr[y].lc) { tr[y].lc=tr[x].rc; if(tr[y].lc) tr[tr[y].lc].fa=y; tr[x].fa=z; if(tr[z].lc==y) tr[z].lc=x; else tr[z].rc=x; tr[x].rc=y; tr[y].fa=x; } else { tr[y].rc=tr[x].lc; tr[tr[y].rc].fa=y; tr[x].fa=z; if(tr[z].lc==y) tr[z].lc=x; else tr[z].rc=x; tr[x].lc=y; tr[y].fa=x; } setup(y); setup(x); } void splay(int x,int p) { int y,z; while(tr[x].fa!=p) { y=tr[x].fa; z=tr[y].fa; if(z==p) { xuan(x); } else { if(tr[y].lc==x) { if(tr[z].lc==y) xuan(y); else xuan(x); xuan(x); } else { if(tr[z].rc==y) xuan(y); else xuan(x); xuan(x); } } } if(p==0) root=x; } int findmin(int a) { if(!tr[a].lc) return a; else return findmin(tr[a].lc); } int findmax(int a) { if(!tr[a].rc) return a; else return findmax(tr[a].rc); } void shan(int i) { splay(i,0); int a=findmax(tr[i].lc); int b=findmin(tr[i].rc); splay(a,0); splay(b,a); tr[b].lc=0; setup(b); setup(a); } int find(int i,int x) { if(root==i) if(x>=tr[i].size) return -change-1; if(tr[tr[i].rc].size>=x&&tr[i].rc) return find(tr[i].rc,x); if(tr[tr[i].rc].size+1==x) return tr[i].w; if(tr[tr[i].rc].size+1<=x) return find(tr[i].lc,x-tr[tr[i].rc].size-1); } int main() { // freopen("1.txt","r",stdin); scanf("%d%d",&n,&jx); char a1; int a2; jia(0,-100000000); jia(1,100000000); root=2; while(n--) { // a1=getchar(); scanf("%c",&a1); while(a1<41) scanf("%c",&a1); scanf("%d",&a2); if(a1=='I'&&a2>=jx) { jia(root,a2-change); splay(tott,0); put(tott,a2-change); } if(a1=='A') change+=a2; if(a1=='S') { change-=a2; while(dui[1].w+change<jx&&totd) { shan(dui[1].pr); pop(); leave++; } } if(a1=='F') printf("%d\n",find(root,a2+1)+change); } printf("%d",leave); return 0; }