[BZOJ4864][BeiJing 2017 Wc]神秘物质（splay）

题目描述

传送门

题目大意： 有一列数列，支持以下操作 对于一列数，相邻一段中最大和最小的两个数的差值称为区间极差。 merge x e 当前第 x 个数和第 x+1 个数合并，得到值为 e 的新数； insert x e 在当前第 x 个数和第 x+1 个数之间插入一个能量为 e 的新数。 max x y 当前第 x 到第 y 个原子之间的任意子区间中区间极差的最大值； min x y 当前第 x 到第 y 个原子之间的任意子区间中区间极差的最小值。

题解

用splay维护：子树大小，区间最大最小值，区间最左端最右端的数值，相邻两个元素差值的最小值 因为min操作实际上就是查询相邻两个元素差值的最小值 其余的随便做咯

代码

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define N 200005 #define inf 1000000001 int n,m,root,sz,a[N]; int f[N],ch[N][2],key[N],size[N],ls[N],rs[N],maxn[N],minn[N],cha[N]; char opt[10]; int Abs(int x){return (x>0)?x:-x;} void update(int x) { int l=ch[x][0],r=ch[x][1]; size[x]=1;cha[x]=inf; maxn[x]=minn[x]=ls[x]=rs[x]=key[x]; if (l) { ls[x]=ls[l];size[x]+=size[l]; maxn[x]=max(maxn[x],maxn[l]); minn[x]=min(minn[x],minn[l]); cha[x]=min(cha[x],cha[l]); cha[x]=min(cha[x],Abs(key[x]-rs[l])); } if (r) { rs[x]=rs[r];size[x]+=size[r]; maxn[x]=max(maxn[x],maxn[r]); minn[x]=min(minn[x],minn[r]); cha[x]=min(cha[x],cha[r]); cha[x]=min(cha[x],Abs(key[x]-ls[r])); } } int build(int l,int r,int fa) { if (l>r) return 0; int mid=(l+r)>>1; f[mid]=fa;key[mid]=a[mid]; int lch=build(l,mid-1,mid); int rch=build(mid+1,r,mid); ch[mid][0]=lch;ch[mid][1]=rch; update(mid); return mid; } int get(int x){return ch[f[x]][1]==x;} void rotate(int x) { int old=f[x],oldf=f[old],wh=get(x); ch[old][wh]=ch[x][wh^1]; if (ch[old][wh]) f[ch[old][wh]]=old; ch[x][wh^1]=old; f[old]=x; if (oldf) ch[oldf][ch[oldf][1]==old]=x; f[x]=oldf; update(old); update(x); } void splay(int x,int tar) { for (int fa;(fa=f[x])!=tar;rotate(x)) if (f[fa]!=tar) rotate((get(x)==get(fa))?fa:x); if (!tar) root=x; } int find(int x) { int now=root; while (1) { if (ch[now][0]&&size[ch[now][0]]>=x) now=ch[now][0]; else { if (ch[now][0]) x-=size[ch[now][0]]; if (x==1) return now; --x; now=ch[now][1]; } } } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) scanf("%d",&a[i+1]); root=build(1,n+2,0);sz=n+2; while (m--) { scanf("%s",opt); if (opt[0]=='m'&&opt[1]=='e') { int x,e;scanf("%d%d",&x,&e); // x x+1 int aa=find(x); int bb=find(x+3); splay(aa,0); splay(bb,aa); //delete ch[ch[root][1]][0]=0; //insert ++sz; f[sz]=ch[root][1];ch[ch[root][1]][0]=sz; size[sz]=1;cha[sz]=inf; key[sz]=maxn[sz]=minn[sz]=ls[sz]=rs[sz]=e; update(ch[root][1]); update(root); } else if (opt[0]=='i') { int x,e;scanf("%d%d",&x,&e); //x,x+1 int aa=find(x+1); int bb=find(x+2); splay(aa,0); splay(bb,aa); //insert ++sz; size[sz]=1;cha[sz]=inf; f[sz]=ch[root][1];ch[ch[root][1]][0]=sz; key[sz]=maxn[sz]=minn[sz]=ls[sz]=rs[sz]=e; update(ch[root][1]); update(root); } else if (opt[0]=='m'&&opt[1]=='a') { int x,y;scanf("%d%d",&x,&y); //x y int aa=find(x); int bb=find(y+2); splay(aa,0); splay(bb,aa); //query int now=ch[ch[root][1]][0]; printf("%d\n",maxn[now]-minn[now]); } else { int x,y;scanf("%d%d",&x,&y); //x y int aa=find(x); int bb=find(y+2); splay(aa,0); splay(bb,aa); //query int now=ch[ch[root][1]][0]; printf("%d\n",cha[now]); } } }