P1110 [ZJOI2007]报表统计

皎月半洒花

2018-05-10 21:32:07

Solution

这个题是真毒瘤……我足足调试了19个小时,换了四种不同的写法,跑去问了机房里炒鸡厉害的大佬$qyf$3次才把它在$TLE$的条件下开$O_2AC$了$ORZZZZ$. 代码量$7k$(由于不会写成员函数所以代码长的很) 所以我是真的菜。 哦,这道题的难度在我这个不会写成员函数的蒟蒻看来,应该算是一道好题了,因为它并没有其他的紫题那样水。 哦,您觉得简单,那您强好了。 那么其实很显然,这个题我们可以用堆(失败),可以用$STL$ 里的$set$,也可以用两棵平衡树。而在这里我由于不想手写堆,所以用的$STL$结果炸了。 那么,一棵平衡树维护最小不相邻差值,一棵平衡树维护最小相邻差值,前者不带删除,后者带删除。 ## 维护不相邻最小差值: 每次插入一个数时,找它的前驱后继,然后更新答案变量$minn$. ## 维护相邻最小差值: 我们记录一下原序列每个元素之后插入的元素中最后插入的数。然后每次$insert$之后删除一次插入两次即可。 $Code$: 我辣鸡,凑合着看吧。 当然,我不会写成员函数(其实是一开始没用成员函数之后,写了一半懒得用了)。 ```cpp #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #define MAXN 500001 #define Inf 2147483600 #define ll long long using namespace std; struct tree{ ll v,sub,son[2],f,cnt; }s[MAXN<<1],S[MAXN<<1]; ll minn=Inf,root,wz,num[MAXN],base[MAXN],i,now,res,pre,suffix,fa; ll _res,_wz,_root,_now,_fa,_rank,_old_root; inline long long qread(){ long long num=0; char ch=getchar(); while(!isdigit(ch)){ ch=getchar(); } while(isdigit(ch)){ num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num; } /*___________________________________________________________*/ inline ll my_abs(ll x){ return x>0?x:-x; } inline bool which(ll x){ return x==s[s[x].f].son[1]; } inline void update(ll x){ if(x){ s[x].sub=s[x].cnt; if(s[x].son[0])s[x].sub+=s[s[x].son[0]].sub; if(s[x].son[1])s[x].sub+=s[s[x].son[1]].sub; } } inline void rotate(ll x){ ll fnow=s[x].f,ffnow=s[fnow].f; bool w=which(x); s[fnow].son[w]=s[x].son[w^1]; s[s[fnow].son[w]].f=fnow; s[fnow].f=x; s[x].f=ffnow; s[x].son[w^1]=fnow; if(ffnow){ s[ffnow].son[s[ffnow].son[1]==fnow]=x; } update(fnow); } inline void splay(ll x,ll goal){ for(ll qwq;(qwq=s[x].f)!=goal;rotate(x)){ if(s[qwq].f!=goal){ rotate(which(x)==which(qwq)?qwq:x); } } if(goal==0){ root=x; } } inline void insert(ll x){ if(!root){ wz++; s[wz].son[0]=s[wz].son[1]=s[wz].f=0; root=wz; s[wz].sub=s[wz].cnt++; s[wz].v=x; return ; } now=root,fa=0; while(1){ if(x==s[now].v){ s[now].cnt++; update(now); update(fa); splay(now,0); break; } fa=now; now=s[now].son[s[now].v<x]; if(!now){ wz++; s[wz].son[0]=s[wz].son[1]=0; s[wz].f=fa; s[wz].sub=s[wz].cnt++; s[fa].son[s[fa].v<x]=wz; s[wz].v=x; update(fa); splay(wz,0); break; } } } inline ll find_pre(){ res=s[s[root].son[0]].v,now=s[root].son[0]; if(s[root].cnt>1) return s[root].v; while(s[now].son[1]){ res=s[s[now].son[1]].v; now=s[now].son[1]; } return res; } inline ll find_suffix(){ res=s[s[root].son[1]].v,now=s[root].son[1]; if(s[root].cnt>1) return s[root].v; while(s[now].son[0]){ res=s[s[now].son[0]].v; now=s[now].son[0]; } return res; } inline void init_insert(ll now){ insert(now); suffix=find_suffix(); pre=find_pre(); if(suffix!=Inf){ minn=min(minn,my_abs(suffix-now)); } if(pre!=-Inf){ minn=min(minn,my_abs(pre-now)); } } /*___________________________________________________________*/ inline bool S_which(ll x){ return x==S[S[x].f].son[1]; } inline void S_clear(ll x){ S[x].cnt=S[x].son[1]=S[x].son[0]=S[x].f=S[x].sub=S[x].v=0; if(x==-wz)_wz--; } inline void S_update(ll x){ if(x){ S[x].sub=S[x].cnt; if(S[x].son[0])S[x].sub+=S[S[x].son[0]].sub; if(S[x].son[1])S[x].sub+=S[S[x].son[1]].sub; } } inline void S_rotate(ll x){ ll fnow=S[x].f,ffnow=S[fnow].f; bool w=S_which(x); S[fnow].son[w]=S[x].son[w^1]; S[S[fnow].son[w]].f=fnow; S[fnow].f=x; S[x].f=ffnow; S[x].son[w^1]=fnow; if(ffnow){ S[ffnow].son[S[ffnow].son[1]==fnow]=x; } S_update(fnow); } inline void S_splay(ll x,ll goal){ for(ll qwq;(qwq=S[x].f)!=goal;S_rotate(x)){ if(S[qwq].f!=goal){ S_rotate(S_which(x)==S_which(qwq)?qwq:x); } } if(goal==0){ _root=x; } } inline void S_insert(ll x){ if(!_root){ _wz++; S[_wz].son[0]=S[_wz].son[1]=S[_wz].f=0; _root=_wz; S[_wz].sub=S[_wz].cnt++; S[_wz].v=x; return ; } _now=_root,_fa=0; while(1){ if(x==S[_now].v){ S[_now].cnt++; S_update(_now); S_update(_fa); S_splay(_now,0); break; } _fa=_now; _now=S[_now].son[S[_now].v<x]; if(!_now){ _wz++; S[_wz].son[0]=S[_wz].son[1]=0; S[_wz].f=_fa; S[_wz].sub=S[_wz].cnt++; S[_fa].son[S[_fa].v<x]=_wz; S[_wz].v=x; S_update(_fa); S_splay(_wz,0); break; } } } inline ll S_find_pre(){ _now=S[_root].son[0]; while(S[_now].son[1]){ _now=S[_now].son[1]; } return _now; } inline ll S_find_rank(ll x){ _now=_root,_rank=0; while(1){ if(x<S[_now].v){ _now=S[_now].son[0]; } else { _rank+=(S[_now].son[0]?S[S[_now].son[0]].sub:0); if(x==S[_now].v){ S_splay(_now,0); return _rank+1; } _rank+=S[_now].cnt; _now=S[_now].son[1]; } } } inline ll S_find_num(ll x){ _now=_root; while(1){ if(S[_now].son[0]&&x<=S[S[_now].son[0]].sub){ _now=S[_now].son[0]; } else { ll temp=(S[_now].son[0]?S[S[_now].son[0]].sub:0)+S[_now].cnt; if(x<=temp)return S[_now].v; x-=temp; _now=S[_now].son[1]; } } } inline void S_delete(ll x){ int hhh=S_find_rank(x); if(S[_root].cnt>1){ S[_root].cnt--; S_update(_root); return ; } if(!S[_root].son[0]&&!S[_root].son[1]){ S_clear(_root); _root=0; return ; } if(!S[_root].son[0]){ _old_root=_root; _root=S[_root].son[1]; S[_root].f=0; S_clear(_old_root); return ; } if(!S[_root].son[1]){ _old_root=_root; _root=S[_root].son[0]; S[_root].f=0; S_clear(_old_root); return ; } int left_max=S_find_pre(),_old_root=_root; S_splay(left_max,0); S[_root].son[1]=S[_old_root].son[1]; S[S[_old_root].son[1]].f=_root; S_clear(_old_root); S_update(_root); } /*___________________________________________________________*/ int main(){ ll a,n,m,b; char s[20]; cin>>n>>m; insert(Inf); insert(-Inf); for(i=1;i<=n;i++){ base[i]=num[i]=qread(); if(i!=1)S_insert(my_abs(base[i-1]-base[i])); init_insert(base[i]); } for(register int i=1;i<=m;i++){ scanf("%s",s); int ss=strlen(s); if(ss==7) { printf("%d\n",S_find_num(1)); continue; } else if(ss==12){ printf("%d\n",minn); continue; } else { a=qread(); b=qread(); if(a<n){ S_delete(my_abs(num[a]-base[a+1])); S_insert(my_abs(b-base[a+1])); } S_insert(my_abs(b-num[a])); init_insert(b); num[a]=b; continue; } } } ``` # $\color{gold}Think$ $~$ $\color{silver}Twice$ $,$ $\color{cyan}Code$ $~$ $\color{red}Once.$