首页 > 代码库 > bzoj 1503 郁闷的出纳员
bzoj 1503 郁闷的出纳员
平衡树维护。
treap还是引用版的好写,自带大代码量写非引用版的估计要300行+。
删除的时候各种pushup不太好理解。
注意刚来就走的员工不算在最后一问里。
删除一个值要减去这个值的所有员工数,直接减一wa半天。
1 #include<cstring> 2 #include<cstdio> 3 #include<algorithm> 4 #include<iostream> 5 #include<cstdlib> 6 using namespace std; 7 const int dian=100005; 8 int aa[1000005]; 9 int ky[dian],pr[dian],ch[dian][3],siz[dian],num[dian]; 10 char flag[10]; 11 int n,m,a; 12 int len,cnt,root,summ; 13 int rd(){ 14 int xx=rand()%1000; 15 int yy=rand()%1000; 16 int zz=xx*1000+yy+1; 17 zz=zz%len+1; 18 int lala=aa[zz]; 19 aa[zz]=aa[len]; 20 len--; 21 return lala; 22 } 23 void pushup(int x){ 24 siz[x]=siz[max(0,ch[x][0])]+siz[max(0,ch[x][1])]+num[x]; 25 } 26 void rotate(int &k,int ok){ 27 int t=ch[k][ok]; 28 ch[k][ok]=ch[t][ok^1]; 29 ch[t][ok^1]=k; 30 pushup(k),pushup(t); 31 k=t; 32 } 33 void insert(int &k,int tkey){ 34 if(k==-1){ 35 k=++cnt; 36 ky[k]=tkey; 37 pr[k]=rd(); 38 ch[k][0]=-1; 39 ch[k][1]=-1; 40 num[k]=1; 41 siz[k]=1; 42 } 43 else{ 44 siz[k]++; 45 if(tkey==ky[k]) 46 num[k]++; 47 else if(tkey<ky[k]){ 48 insert(ch[k][0],tkey); 49 if(pr[ch[k][0]]<pr[k]) 50 rotate(k,0); 51 } 52 else{ 53 insert(ch[k][1],tkey); 54 if(pr[ch[k][1]<pr[k]]) 55 rotate(k,1); 56 } 57 } 58 } 59 void del(int &k){ 60 if(ch[k][0]==-1&&ch[k][1]==-1) 61 k=-1; 62 else if(ch[k][0]==-1) 63 k=ch[k][1]; 64 else if(ch[k][1]==-1) 65 k=ch[k][0]; 66 else if(pr[ch[k][0]]<pr[ch[k][1]]){ 67 rotate(k,0); 68 del(ch[k][1]); 69 pushup(k); 70 } 71 else{ 72 rotate(k,1); 73 del(ch[k][0]); 74 pushup(k); 75 } 76 } 77 void add(int k,int x){ 78 if(k==-1) 79 return; 80 ky[k]+=x; 81 add(ch[k][0],x); 82 add(ch[k][1],x); 83 } 84 void dec(int &k,int x){ 85 while(ky[k]-x<m&&k!=-1){ 86 summ+=num[k]; 87 del(k); 88 } 89 if(k==-1) 90 return; 91 ky[k]-=x; 92 dec(ch[k][0],x); 93 dec(ch[k][1],x); 94 pushup(k); 95 } 96 int find(int k,int rank){ 97 if(rank-siz[max(0,ch[k][1])]>=1&&rank-siz[max(0,ch[k][1])]<=num[k]) 98 return ky[k]; 99 else if(siz[max(0,ch[k][1])]>=rank) 100 return find(ch[k][1],rank); 101 else 102 return find(ch[k][0],rank-siz[max(ch[k][1],0)]-num[k]); 103 } 104 int main(){ 105 for(int i=1;i<=1000000;i++) 106 aa[i]=i; 107 len=1000000; 108 cnt=0; 109 root=-1; 110 summ=0; 111 srand(1600158127); 112 scanf("%d%d",&n,&m); 113 for(int i=1;i<=n;i++){ 114 scanf("%s%d",flag,&a); 115 if(flag[0]==‘I‘){ 116 if(a<m) 117 continue; 118 insert(root,a); 119 } 120 else if(flag[0]==‘A‘) 121 add(root,a); 122 else if(flag[0]==‘S‘) 123 dec(root,a); 124 else{ 125 if(a>siz[root]) 126 printf("-1\n"); 127 else 128 printf("%d\n",find(root,a)); 129 } 130 } 131 printf("%d\n",summ); 132 return 0; 133 }
为什么我写得这么长!
bzoj 1503 郁闷的出纳员
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。