splay jzoj4986 神秘物质

题目

Description Input Sample Input

输入1：

4 3 5 8 10 2 max 1 3 min 1 3 max 2 4 输入2：

6 7 1 2 3 4 5 6 insert 1 3 max 2 4 merge 1 2 max 2 4 min 2 4 insert 6 1 max 5 7

Output Sample Output

输出1：

5 2 8

输出2：

1 2 1 5 Data Constraint Hint

题解

首先这一道题是移到splay的裸题 然后我们首先考虑如何处理max和min 容易发现max就是一段区间里的最大值减去最小值 而min则是一段区间里相邻的两个值的差的最小值 我们考虑用splay来维护这两个东西 首先我们可以用bg[x]和sm[x]表示以x为根的子树里面的最大值和最小值，这样我们就解决了max 然后我们可以用zi[x]来表示以x为根的子树里面的“min”操作的答案 那么zi[x]等于x两个儿子的zi值，x左儿子的一直右儿子的值减去x的值以及x的右儿子的一直左儿子的值减去x的值4个值里面最小的值 那么x左儿子的一直右儿子的值减去x的值以及x的右儿子的一直左儿子的值怎么怎么维护呢？ 一开始我并没有想到，然后就死维护，然后就。。。错了。。。 可以发现其实那两个点就是next[x]和last[x]（表示序列里的x+1，x-1号节点），但是如我们还要考虑x没有右儿子/左儿子的情况（一开始我就没有考虑这个东西） 然后两个修改操作都挺好搞的，就是insert的时候注意可能插到最后一个节点的后面，这是要特殊处理

贴代码

#include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> #include<math.h> using namespace std; const int maxn=150005; int father[maxn],cnt[maxn],data[maxn],zi[maxn],bg[maxn],sm[maxn],next[maxn],last[maxn]; int son[maxn][3]; int i,j,k,l,n,m,root,x,y,z,tot; char s[10]; void rotate(int x,int w){ int y,tmp; y=father[x]; bg[x]=bg[y]; sm[x]=sm[y]; zi[x]=zi[y]; bg[y]=max(max(bg[son[y][w]],bg[son[x][w]]),data[y]); sm[y]=data[y]; if (sm[son[y][w]]) sm[y]=min(sm[y],sm[son[y][w]]); if (sm[son[x][w]]) sm[y]=min(sm[y],sm[son[x][w]]); //sm[y]=min(min(sm[son[y][w]],sm[son[x][w]]),data[y]); cnt[y]=cnt[y]-cnt[x]+cnt[son[x][w]]; cnt[x]=cnt[x]+cnt[y]-cnt[son[x][w]]; father[x]=father[y]; if (father[y]){ if (y==son[father[y]][1]) son[father[y]][1]=x; else son[father[y]][2]=x; } son[y][3-w]=son[x][w]; if (son[x][w]) father[son[x][w]]=y; father[y]=x; son[x][w]=y; zi[y]=0x7fffffff; if (son[y][1]) zi[y]=min(zi[y],zi[son[y][1]]); if (son[y][2]) zi[y]=min(zi[y],zi[son[y][2]]); if (next[y]&&son[y][2]!=0) zi[y]=min(zi[y],abs(data[next[y]]-data[y])); if (last[y]&&son[y][1]!=0) zi[y]=min(zi[y],abs(data[last[y]]-data[y])); } void splay(int x){ int y; while (father[x]){ y=father[x]; if (!father[y]){ if (son[y][1]==x) rotate(x,2); else rotate(x,1); } else{ if (y==son[father[y]][1]){ if (son[y][1]==x){ rotate(y,2); rotate(x,2); } else{ rotate(x,1); rotate(x,2); } } else{ if (son[y][1]==x){ rotate(x,2); rotate(x,1); } else{ rotate(y,1); rotate(x,1); } } } } root=x; } int kth(int x,int w){ int i; i=root; while ((x!=cnt[son[i][w]]+1) && (i)) { if (x<cnt[son[i][w]]+1){ i=son[i][w]; } else { x=x-cnt[son[i][w]]-1; i=son[i][3-w]; } } splay(i); return root; } int main(){ //freopen("4896.in","r",stdin); //freopen("4986.out","w",stdout); scanf("%d%d",&n,&m); for (i=1;i<=n;i++){ scanf("%d",&data[i]); father[i]=i-1; if (i!=n) son[i][2]=i+1; cnt[i]=n-i+1; if (i!=n) next[i]=i+1; last[i]=i-1; } root=1; tot=n; sm[n+1]=0x7fffffff; zi[n]=0x7fffffff; for (i=n;i>=1;i--){ bg[i]=max(bg[i+1],data[i]); sm[i]=min(sm[i+1],data[i]); if (i!=n) zi[i]=min(zi[i+1],abs(data[i]-data[i+1])); } for (i=1;i<=m;i++){ scanf("%s",&s); if (s[1]=='e'){ scanf("%d%d",&x,&y); x=kth(x,1); father[son[root][2]]=0; z=next[x]; splay(z); root=x; data[x]=y; --cnt[x]; son[x][2]=son[z][2]; father[son[z][2]]=x; data[z]=0; cnt[z]=0; father[z]=0; son[z][1]=0; son[z][2]=0; next[x]=next[z]; last[next[z]]=x; last[z]=0; next[z]=0; data[x]=y; bg[x]=max(max(data[x],bg[son[x][1]]),bg[son[x][2]]); sm[x]=data[x]; if (son[x][1]) sm[x]=min(sm[x],sm[son[x][1]]); if (son[x][2]) sm[x]=min(sm[x],sm[son[x][2]]); zi[x]=0x7fffffff; if (son[x][1]) zi[x]=min(zi[x],zi[son[x][1]]); if (son[x][2]) zi[x]=min(zi[x],zi[son[x][2]]); if (last[x]&&son[x][1]!=0) zi[x]=min(zi[x],abs(data[x]-data[last[x]])); if (next[x]&&son[x][2]!=0) zi[x]=min(zi[x],abs(data[x]-data[next[x]])); } else if (s[1]=='n'){ scanf("%d%d",&x,&y); x=kth(x,1); z=next[x]; tot++; if (next[x]==0){ data[tot]=y; cnt[tot]=1; cnt[x]++; father[tot]=x; son[x][2]=tot; next[x]=tot; last[tot]=x; sm[x]=min(sm[x],y); bg[x]=max(bg[x],y); sm[tot]=tot; bg[tot]=tot; zi[x]=min(zi[x],abs(data[x]-y)); zi[tot]=0x7fffffff; } else{ father[son[x][2]]=0; splay(z); father[z]=x; son[x][2]=z; root=x; data[tot]=y; cnt[tot]=1; father[tot]=z; son[z][1]=tot; l=tot; while (father[l]){ cnt[father[l]]++; l=father[l]; } next[x]=tot; last[tot]=x; next[tot]=z; last[z]=tot; sm[tot]=y; bg[tot]=y; sm[z]=min(sm[z],y); bg[z]=max(bg[z],y); sm[x]=min(sm[x],sm[z]); bg[x]=max(bg[x],bg[z]); zi[tot]=0x7fffffff; zi[z]=min(zi[z],abs(data[z]-y)); zi[x]=min(zi[x],abs(data[x]-y)); } } else if (s[1]=='a'){ scanf("%d%d",&x,&y); y=kth(y,1); x=kth(x,1); father[son[x][2]]=0; splay(y); father[y]=x; son[x][2]=y; z=0x7fffffff; root=x; if (son[y][1]) z=sm[son[y][1]]; printf("%d\n",max(max(bg[son[y][1]],data[x]),data[y])-min(min(z,data[x]),data[y])); } else{ scanf("%d%d",&x,&y); x=kth(x,1); y=kth(y,1); splay(x); father[son[x][2]]=0; splay(y); father[y]=x; son[x][2]=y; root=x; z=0x7fffffff; if (son[y][1]) z=zi[son[y][1]]; l=y; while (son[l][1]) l=son[l][1]; z=min(z,abs(data[x]-data[l])); z=min(z,abs(data[y]-data[last[y]])); printf("%d\n",z); } } return 0; }