电源

【jzoj3740】【TJOI2014】【电源插排】【线段树】

2019-07-13 23:38发布

站内文章 / 电源技术
10547 0 1263

题目大意

这里写图片描述

解题思路

建一棵线段树，动态开点，维护size，最大空区间，左边右边起最大空区间，及其起始点。同时开hash维护所有人站在哪里。

code

#include<set> #include #include #include #include #define LF double #define LL long long #define Min(a,b) ((ab)?a:b) #define Fo(i,j,k) for(int i=j;i<=k;i++) #define Fd(i,j,k) for(int i=j;i>=k;i--) #define For(i,j) for(int i=Begin[j];i;i=Next[i]) using namespace std; int const Mxn=1e5,Mxm=3*1e6; int N,Q,Pon=1,H[Mxn+9],Pos[Mxn+9],Ans[Mxm+9],Lans[Mxm+9],Rans[Mxm+9], Size[Mxm+9],Beg[Mxm+9],Beg2[Mxm+9],Son[Mxm+9][2]; int Hash(int X){ int Tmp=X%Mxn; while(H[Tmp]&&(H[Tmp]!=X))Tmp=(Tmp+1==Mxn)?0:Tmp+1; H[Tmp]=X; return Tmp; } void Oper(int Now,int L,int R,int U,int V){ int Mid=(L+R)>>1; if(L==R){ Size[Now]+=V; Lans[Now]=Rans[Now]=Ans[Now]=V<0; Beg[Now]=Beg2[Now]=L; return; } if(U<=Mid){ Son[Now][0]=(Son[Now][0])?Son[Now][0]:++Pon; Oper(Son[Now][0],L,Mid,U,V); }else{ Son[Now][1]=(Son[Now][1])?Son[Now][1]:++Pon; Oper(Son[Now][1],Mid+1,R,U,V); } if(!Son[Now][0])Ans[0]=Lans[0]=Rans[0]=Mid-L+1,Beg[0]=Beg2[0]=L; if(!Son[Now][1])Ans[0]=Lans[0]=Rans[0]=R-Mid,Beg[0]=Beg2[0]=Mid+1; int Tmp,Tmp2; if(Ans[Son[Now][0]]>Ans[Son[Now][1]]) Tmp=Beg[Son[Now][0]],Tmp2=Ans[Son[Now][0]]; else Tmp=Beg[Son[Now][1]],Tmp2=Ans[Son[Now][1]]; if((Rans[Son[Now][0]]+Lans[Son[Now][1]]>Tmp2)|| ((Rans[Son[Now][0]]+Lans[Son[Now][1]]==Tmp2)&&(Beg2[Son[Now][0]]>Tmp))) Tmp=Beg2[Son[Now][0]],Tmp2=Rans[Son[Now][0]]+Lans[Son[Now][1]]; Beg[Now]=Tmp;Ans[Now]=Tmp2; Lans[Now]=(Lans[Son[Now][0]]==(Mid-L+1))?Mid-L+1+Lans[Son[Now][1]]: Lans[Son[Now][0]]; if((Rans[Son[Now][1]]==R-Mid)&&Rans[Son[Now][0]]){ Rans[Now]=R-Mid+Rans[Son[Now][0]]; Beg2[Now]=Beg2[Son[Now][0]]; }else{ Rans[Now]=Rans[Son[Now][1]]; Beg2[Now]=Beg2[Son[Now][1]]; } Size[Now]=Size[Son[Now][0]]+Size[Son[Now][1]]; Ans[0]=Lans[0]=Rans[0]=0; } int Qury(int Now,int L,int R,int U,int V){ int Mid=(L+R)>>1; if((L==U)&&(R==V))return Size[Now]; if(V<=Mid)return (Son[Now][0])?Qury(Son[Now][0],L,Mid,U,V):0; else if(MidNow][1])?Qury(Son[Now][1],Mid+1,R,U,V):0; else return ((Son[Now][0])?Qury(Son[Now][0],L,Mid,U,Mid):0)+ ((Son[Now][1])?Qury(Son[Now][1],Mid+1,R,Mid+1,V):0); } int main(){ freopen("switch.in","r",stdin); freopen("switch.out","w",stdout); scanf("%d%d",&N,&Q); Beg[1]=1;Ans[1]=N; Fo(cas,1,Q){ int K;scanf("%d",&K); if(K){ int Tmp=Hash(K); if(Pos[Tmp]){ Oper(1,1,N,Pos[Tmp],-1); Pos[Tmp]=0; continue; } Pos[Tmp]=Beg[1]+Ans[1]/2; Oper(1,1,N,Pos[Tmp],1); int bb; bb++; }else{ int L,R;scanf("%d%d",&L,&R); printf("%d ",Qury(1,1,N,L,R)); } } return 0; }

热门文章