一杯茶，一包烟，一道水题调一天
这题一眼看上去就是个裸板子对吧
本来以为要两棵splay，读了一下题发现店里只能有一种生物（人/宠物）
所以记录一下当前店里的状态就行了
老年手速20min过编译，
嗯？
检查了30min发现没取mod
嗯？
检查调试对拍了2h+30min重构代码
发现Splay打错了
int nxt() { if(cnt[root]>1)return root; int now=son[root][1]; while(son[now][0])now=son[now][0]; return now; } //√ int nxt() { if(cnt[root]>1)return root; int now=son[root][1]; while(son[now][1])now=son[now][0]; return now; } //×
我打的时候在想什么啊啊啊啊啊身败名裂辽
总结：数据结构题如果迟迟调不过 不如检查一下是否在数据结构本身上犯了白痴错误
#include<cstdio> #include<iostream> #include<cstring> #include<cmath> using namespace std; const int N=100005,mod=1e6,inf=0x3f3f3f3f; int fa[N],cnt[N],son[N][3],size[N],key[N],type,root; int n,num[3]; void clear(int x) { fa[x]=cnt[x]=son[x][0]=son[x][1]=size[x]=key[x]=0; } bool judge(int x) { return son[fa[x]][1]==x; } void up(int x) { if(x) { size[x]=cnt[x]; if(son[x][0])size[x]+=size[son[x][0]]; if(son[x][1])size[x]+=size[son[x][1]]; } } void rotate(int x) { int old=fa[x],oldf=fa[old],lr=judge(x); son[old][lr]=son[x][lr^1]; fa[son[old][lr]]=old; son[x][lr^1]=old; fa[old]=x; fa[x]=oldf; if(oldf)son[oldf][son[oldf][1]==old]=x; up(old);up(x); } void splay(int x) { for(int f;f=fa[x];rotate(x)) if(fa[f])rotate(judge(x)==judge(f)?f:x); root=x; } void ins(int x) { if(!root) { type++; key[type]=x; root=type; cnt[type]=size[type]=1; fa[type]=son[type][0]=son[type][1]=0; return ; } int now=root,f=0; while(1) { if(x==key[now]) { cnt[now]++; up(now); up(f); splay(now); return ; } f=now;now=son[now][key[now]<x]; if(!now) { type++; size[type]=cnt[type]=1; son[type][0]=son[type][1]=0; son[f][x>key[f]]=type; fa[type]=f; key[type]=x; up(f);splay(type); return ; } } } int pre() { if(cnt[root]>1)return root; int now=son[root][0]; while(son[now][1])now=son[now][1]; return now; } int nxt() { if(cnt[root]>1)return root; int now=son[root][1]; while(son[now][0])now=son[now][0]; return now; } void changeroot(int x) { int now=root; while(1) { if(x<key[now])now=son[now][0]; else { if(x==key[now]) { splay(now); return ; } now=son[now][1]; } } } void del(int x) { changeroot(x); if(cnt[root]>1) { cnt[root]--; up(root); return ; } if(!son[root][0]&&!son[root][1]) { clear(root); root=0; return ; } if(!son[root][0]) { int old=root; root=son[root][1]; fa[root]=0; clear(old); return ; } else if(!son[root][1]) { int old=root; root=son[root][0]; fa[root]=0; clear(root); return ; } int old=root,L=pre(); splay(L); son[root][1]=son[old][1]; fa[son[old][1]]=root; clear(old); up(root); } inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } int now_=-1; int ans; int main() { n=read(); ins(inf);ins(-inf); for(int i=1;i<=n;i++) { int op=read(),val=read(); //cout<<"root="<<root<<endl; if(now_==-1) { now_=op; ins(val); num[op]++; continue; } if(now_==op) { ins(val); num[op]++; continue; } ins(val); int pre_=pre(),nxt_=nxt(),preval=key[pre_],nxtval=key[nxt_]; del(val); if(val-preval<=nxtval-val)ans+=(val-preval)%mod,del(preval),num[op^1]--; else ans+=(nxtval-val)%mod,del(nxtval),num[op^1]--; if(num[0]==0&&num[1]==0)now_=-1; ans%=mod; } cout<<ans%mod<<endl; return 0; }