P4032 「CodePlus 2017 12 月赛」火锅盛宴(splay+堆)

hhz6830975

2018-01-16 13:33:59

Solution

离线读入操作,按时间排序 分别开两个splay维护煮熟的(T[0])和加入但未煮熟的(T[1])食物,关键字都为t 其中T[1]要在每个结点按煮熟的时间(t+s[i])维护一个小根堆(这里直接用stl的优先队列) 操作0可以分解为:t时刻将食物插入T[1];t+s[i]时刻将食物从T[1]删除,将食物插入T[0] 操作1:找T[0]最小值,删除;若T[0]空则angry 操作2:找T[0]中id为k的食物,删除;不存在时找T[1]中id为k的结点,输出堆顶元素-当前时间;不存在该结点则angry 操作3:splay出T[0]对应区间,返回size ps1:写个splay调了半天,最后发现其实可以用树状数组。。 ps2:千万不要和我一样手贱把优先队列塞进结构体,两个树一起开,否则会有奇怪的RE(似乎是优先队列有数量限制?不是很懂) ps3:有多组数据,记得初始化(包括清空优先队列) 代码: ```cpp #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int maxn=100010; const int maxq=500010; const int INF=0x7fffffff; int dT,n,Q,s[maxn],ans[maxq]; inline int read(){ int ret=0,sign=1; char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-') sign=-1; ch=getchar();} while(ch>='0'&&ch<='9') {ret=ret*10+ch-'0'; ch=getchar();} return ret*sign; } int Acnt,Ccnt; struct cmd{ int no,t,op,x,y; }A[2][maxq],C[maxq]; bool cmp(cmd a,cmd b){return a.t<b.t;} priority_queue <int,vector<int>,greater<int> > pq[maxq]; int root[2],Tcnt[2]; struct node{ int fa,son[2],cnt,size,val; node(){} node(int _fa,int lson,int rson,int _val){fa=_fa,son[0]=lson,son[1]=rson,cnt=size=1,val=_val;} }T[2][maxq]; inline int get(int Tn,int u){return T[Tn][T[Tn][u].fa].son[1]==u;} inline void pushup(int Tn,int u){T[Tn][u].size=T[Tn][u].cnt+T[Tn][T[Tn][u].son[0]].size+T[Tn][T[Tn][u].son[1]].size;} inline void rotate(int Tn,int u){ int v=T[Tn][u].fa,rela=get(Tn,u); if(T[Tn][v].fa) T[Tn][T[Tn][v].fa].son[get(Tn,v)]=u; T[Tn][u].fa=T[Tn][v].fa; if(T[Tn][u].son[rela^1]) T[Tn][T[Tn][u].son[rela^1]].fa=v; T[Tn][v].son[rela]=T[Tn][u].son[rela^1]; T[Tn][u].son[rela^1]=v,T[Tn][v].fa=u; pushup(Tn,v),pushup(Tn,u); } inline void splay(int Tn,int u,int final){ while(T[Tn][u].fa!=final){ int v=T[Tn][u].fa; if(T[Tn][v].fa!=final) rotate(Tn,get(Tn,u)==get(Tn,v)?v:v); rotate(Tn,u); } if(final==0) root[Tn]=u; } inline void ins(int Tn,int x,int t=0){ if(!root[Tn]){ T[Tn][++Tcnt[Tn]]=node(0,0,0,x); if(Tn) pq[Tcnt[Tn]].push(t); root[Tn]=Tcnt[Tn]; return; } int u=root[Tn],v=0; while(1){ if(!u) {T[Tn][++Tcnt[Tn]]=node(v,0,0,x),u=Tcnt[Tn],T[Tn][v].son[x>T[Tn][v].val]=u; break;} else if(x==T[Tn][u].val) {++T[Tn][u].cnt,++T[Tn][u].size; break;} else if(x<T[Tn][u].val) v=u,u=T[Tn][u].son[0]; else v=u,u=T[Tn][u].son[1]; } if(Tn) pq[u].push(t); splay(Tn,u,0); } inline int find(int Tn,int u,int x,int final){ while(1){ if(x==T[Tn][u].val) break; else if(x<T[Tn][u].val) u=T[Tn][u].son[0]; else u=T[Tn][u].son[1]; } splay(Tn,u,final); return u; } inline void del(int Tn,int x,int tar=0){ int u; if(tar) splay(Tn,tar,0),u=tar; else u=find(Tn,root[Tn],x,0); if(Tn) pq[u].pop(); if(T[Tn][u].cnt>1) --T[Tn][u].cnt,--T[Tn][u].size; else if(!T[Tn][u].son[0]||!T[Tn][u].son[1]){ int v=T[Tn][u].son[0]!=0?T[Tn][u].son[0]:T[Tn][u].son[1]; T[Tn][v].fa=0,root[Tn]=v; } else{ int v=T[Tn][u].son[0]; while(T[Tn][v].son[1]) v=T[Tn][v].son[1]; splay(Tn,v,0); T[Tn][T[Tn][u].son[1]].fa=v,T[Tn][v].son[1]=T[Tn][u].son[1]; pushup(Tn,v); } } inline int query1(){ int u,ret; find(0,root[0],0,0),u=find(0,root[0],INF,root[0]),u=T[0][u].son[0]; if(!u) return -1; while(T[0][u].son[0]) u=T[0][u].son[0]; ret=T[0][u].val; del(0,0,u); return ret; } inline int query2(int x){ int u=root[0],fail=0; while(1){ if(!u) {fail=1; break;} else if(x==T[0][u].val) break; else if(x<T[0][u].val) u=T[0][u].son[0]; else u=T[0][u].son[1]; } if(!fail){ del(0,0,u); return -2; } u=root[1],fail=0; while(1){ if(!u) {fail=1; break;} else if(x==T[1][u].val) break; else if(x<T[1][u].val) u=T[1][u].son[0]; else u=T[1][u].son[1]; } if(!fail) return pq[u].top(); return -3; } inline int pre(int x){ int u,ret; ins(0,x); u=T[0][root[0]].son[0]; while(T[0][u].son[1]) u=T[0][u].son[1]; ret=T[0][u].val; del(0,x); return ret; } inline int nxt(int x){ int u,ret; ins(0,x); u=T[0][root[0]].son[1]; while(T[0][u].son[0]) u=T[0][u].son[0]; ret=T[0][u].val; del(0,x); return ret; } inline int query3(int l,int r){ int u; l=pre(l),r=nxt(r); find(0,root[0],l,0),u=find(0,root[0],r,root[0]),u=T[0][u].son[0]; return T[0][u].size; } int main(){ dT=read(); for(int i=1;i<=dT;i++){ for(int j=1;j<=Tcnt[1];j++) while(!pq[j].empty()) pq[j].pop(); Acnt=Ccnt=0; root[0]=Tcnt[0]=root[1]=Tcnt[1]=0; n=read(); for(int j=1;j<=n;j++) s[j]=read(); Q=read(); int t,op,x,y=0; for(int j=1;j<=Q;j++){ t=read(),op=read(); if(op==0||op==2) x=read(); else if(op==3) x=read(),y=read(); if(op==0){ ++Acnt; A[0][Acnt]=(cmd){Acnt,t,op,x,0}; A[1][Acnt]=(cmd){Acnt,t+s[x],op,x,0}; } else C[++Ccnt]=(cmd){Ccnt,t,op,x,y}; } sort(A[0]+1,A[0]+Acnt+1,cmp); sort(A[1]+1,A[1]+Acnt+1,cmp); sort(C+1,C+Ccnt+1,cmp); ins(0,0),ins(0,INF);//为splay区间操作方便额外加两个结点 int p0=1,p1=1; for(int j=1;j<=Ccnt;j++){ while(A[0][p0].t<=C[j].t&&p0<=Acnt) ins(1,A[0][p0].x,A[0][p0].t+s[A[0][p0].x]),++p0; while(A[1][p1].t<=C[j].t&&p1<=Acnt) del(1,A[1][p1].x),ins(0,A[1][p1].x),++p1; if(C[j].op==1) ans[C[j].no]=query1(); else if(C[j].op==2) {ans[C[j].no]=query2(C[j].x); if(ans[C[j].no]>0) ans[C[j].no]-=C[j].t;} else ans[C[j].no]=query3(C[j].x,C[j].y); } for(int j=1;j<=Ccnt;j++){ if(ans[j]>=0) printf("%d\n",ans[j]); else if(ans[j]==-1) printf("Yazid is angry.\n"); else if(ans[j]==-2) printf("Succeeded!\n"); else printf("YJQQQAQ is angry.\n"); } } return 0; } ```