这道题应该很快看出是平衡树吧。对于每次操作,相当于是在维护好的平衡树上找前驱和后继。一开始我想的是维护两棵平衡树,一棵宠物树,一棵是人树。但是我这样搞就非常傻逼,而且非常难调。其实只用维护一棵平衡树就够了,用一个变量来记录当前是宠物多还是人多,在树上查询前驱和后继就可以了。
坑点:
1.一开始要加入两个哨兵节点,不然容易出玄学错误。
2.求和的时候要加绝对值abs。
3.第八个点是0,但是我输出的是负数??需要特判才能过。
代码:
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; const int mod=1000000; const int inf=0x7fffffff; int n; int opt,a; int flag; long long sum; int fa1[maxn],key1[maxn],ch1[maxn][2],cnt1[maxn],siz1[maxn]; int rt1,sz1; bool check1(int x){ return ch1[fa1[x]][1]==x; } void pushup1(int x){ siz1[x]=siz1[ch1[x][1]]+siz1[ch1[x][0]]+cnt1[x]; } void clear1(int x){ siz1[x]=cnt1[x]=fa1[x]=ch1[x][0]=ch1[x][1]=key1[x]=0; } void rotate1(int x){ int y=fa1[x],z=fa1[y],who=check1(x); ch1[y][who]=ch1[x][who^1]; fa1[ch1[y][who]]=y; ch1[x][who^1]=y; fa1[y]=x,fa1[x]=z; if(z) ch1[z][ch1[z][1]==y]=x; pushup1(y);pushup1(x); } void splay1(int x,int goal){ for(int f;(f=fa1[x])!=goal;rotate1(x)){ if(fa1[f]!=goal) rotate1((check1(x)==check1(f))?f:x); } if(!goal) rt1=x; } void insert1(int x){ if(!rt1){ rt1=++sz1; cnt1[sz1]=siz1[sz1]=1; key1[sz1]=x; return; } int now=rt1,f=0; while(1){ if(key1[now]==x){ cnt1[now]++; pushup1(f); pushup1(now); splay1(now,0); return; } f=now,now=ch1[now][x>key1[now]]; if(!now){ sz1++; fa1[sz1]=f; ch1[f][x>key1[f]]=sz1; siz1[sz1]=cnt1[sz1]=1; key1[sz1]=x; pushup1(f); splay1(sz1,0); return; } } } int pre1(){ int now=ch1[rt1][0]; while(ch1[now][1]) now=ch1[now][1]; return now; } int nxt1(){ int now=ch1[rt1][1]; while(ch1[now][0]) now=ch1[now][0]; return now; } int rk1(int x){ int now=rt1,ans=0; while(1){ if(x<key1[now]) now=ch1[now][0]; else{ ans+=siz1[ch1[now][0]]; if(x==key1[now]){ splay1(now,0); return ans+1; } ans+=cnt1[now]; now=ch1[now][1]; } } } void del1(int x){ rk1(x); if(cnt1[rt1]>1){ cnt1[rt1]--; pushup1(rt1); return; } if(!ch1[rt1][1]&&!ch1[rt1][0]){ clear1(rt1); rt1=0; return; } if(!ch1[rt1][1]){ int ort=rt1; rt1=ch1[rt1][0]; fa1[rt1]=0; clear1(ort); return; } else if(!ch1[rt1][0]){ int ort=rt1; rt1=ch1[rt1][1]; fa1[rt1]=0; clear1(ort); return; } int ort=rt1,left=pre1(); splay1(left,0); fa1[ch1[ort][1]]=rt1; ch1[rt1][1]=ch1[ort][1]; clear1(ort); pushup1(rt1); } int tot;//判断宠物多还是人多 int main(){ scanf("%d",&n); insert1(inf); insert1(-inf); for(int i=1;i<=n;i++){ scanf("%d%d",&opt,&a); if(!tot) insert1(a); if(tot>0){//pet if(opt==0) insert1(a); else{ insert1(a); int ans1=key1[pre1()]; int ans2=key1[nxt1()]; if(abs(a-ans1)<=abs(ans2-a)){ sum=(long long)(sum+abs(a-ans1))%mod; del1(ans1); } else{ sum=(long long)(sum+abs(ans2-a))%mod; del1(ans2); } del1(a); } } if(tot<0){//customers if(opt==1) insert1(a); else{ insert1(a); int ans1=key1[pre1()]; int ans2=key1[nxt1()]; if(abs(a-ans1)<=abs(ans2-a)){ sum=(long long)(sum+abs(a-ans1))%mod; del1(ans1); } else{ sum=(long long)(sum+abs(ans2-a))%mod; del1(ans2); } del1(a); } } tot=tot+(opt==0?1:-1); } if(sum<0) printf("0\n");//特判,不然有一个点会wa,我也不知道为什么 else printf("%lld\n",sum); return 0; }View Code