假*郁闷的出纳员

出纳员"/>

假*郁闷的出纳员

//一个小时编完了，检查还差一段splay没有写，现在得去上数论QAQ 

//真TM的高兴啊已经写了+调了一个晚上了，就是被TE了，就差几毫秒，真的是几毫秒啊，好气啊

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define maxn 100010 int minn=999999,minsalary=0,n,counting=0,fa[maxn],son[maxn][2],siz[maxn],key[maxn]; int root=1,people=0,leave=0,tip=0; void clear() { memset(fa,0,sizeof(int)); memset(son,0,sizeof(int)); memset(siz,0,sizeof(int)); memset(key,0,sizeof(int)); } int askflag(int now)//direction { if(now==son[fa[now]][0]) return 0;return 1; } void updata(int now) { siz[now]=1+(siz[son[now][0]]+siz[son[now][1]]);// } void rorate(int now) { int father=fa[now],grandpa=fa[fa[now]],flag1=askflag(now),flag2=askflag(fa[now]); if(fa[now]!=-1&&fa[fa[now]]) { son[grandpa][flag2]=now; fa[now]=grandpa; } if(fa[now]==-1)fa[now]=-1,root=now;// fa[son[now][(flag1+1)%2]]=father; son[father][flag1]=son[now][(flag1+1)%2]; fa[father]=now; son[now][(flag1+1)%2]=father; updata(father);updata(now); } void splay(int now,int& root) { fa[root]=-1; while(root!=now) { if(fa[now]!=root&&fa[fa[now]]!=-1) if(askflag(fa[now])!=askflag(now)) rorate(fa[now]); else rorate(now); rorate(now); } } int Kth(int now,int k) { if(siz[son[now][0]]+1==k) return now; if(siz[son[now][0]]+1>k&&son[now][0]) return Kth(son[now][0],k); if(son[now][1]&&siz[son[now][0]]+1<k) return Kth(son[now][1],k-siz[son[now][0]]-1);// return -1; } int getpos(int now,int val) { if(val<key[now]&&siz[son[now][0]]) return getpos(son[now][0],val); if(val>key[now]&&siz[son[now][1]]) return getpos(son[now][1],val); return now; } void insert(int now,int val) { val-=counting; int pos=getpos(root,val); if(!siz[pos]) { key[pos]=val; fa[pos]=0; siz[pos]=1; if(pos!=root) updata(fa[pos]); splay(pos,root); return; } key[now]=val; if(val>key[pos]) {   fa[now]=pos; son[pos][1]=now; siz[now]=1; updata(pos); splay(now,root); } else if(val<key[pos]) { fa[now]=pos; son[pos][0]=now; siz[now]=1; updata(pos); splay(now,root); } else { fa[now]=fa[pos]; siz[pos]++; updata(fa[pos]); splay(now,pos); } } void newnode(int x) { if(x<minsalary) return; insert(++tip,x),++people; if(x-counting<minn) minn=x-counting; } int find(int l,int r) { int mid; while(l<r&&l!=r) { mid=(l+r)>>1; int temp=key[Kth(root,mid)]; if(temp+counting>=minsalary) r=mid; if(temp+counting<minsalary) l=mid+1; } //printf("\nfind %d\n\n",(l+r)>>1); return (l+r)>>1; } void slash(int x) { counting-=x; if(minn+counting>=minsalary) return; int temp=find(1,people); minn=key[temp]; splay(temp,root);//order leave+=siz[son[root][0]];// people-=siz[son[root][0]];//  son[temp][0]=0; siz[son[temp][0]]=0; updata(temp); } void printff() { printf("the salary is "); for(int i=1;i<=tip;i++) if(siz[i])  printf("%d ",key[i]+counting); printf("min/counting/is %d %d\n",minn+counting,counting); } int main() { int temp,t; char c[10],kk; scanf("%d %d",&n,&minsalary); for(int i=1;i<=n;i++) { scanf("%s%d",c,&temp);// kk=c[0]; if(kk=='I') newnode(temp); if(kk=='A') counting+=temp; if(kk=='S') slash(temp); if(kk=='F')  { int t=Kth(root,people-temp+1); if(t!=-1) printf("%d\n",key[t]+counting),splay(t,root); else  printf("-1\n"); } //printff(); } printf("%d\n",leave); }

 

转载于:.html