题解：
splay维护区间最大最小值，以及相邻两项的最小差。
因为向集合中加入元素不能缩小极差。
还有，要换行。
PE2次。
代码：
#include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 100050 #define M 200050 inline int rd() { int f=1,c=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=10*c+ch-'0';ch=getchar();} return f*c; } int n,m,e[N]; const int inf = 0x3f3f3f3f; struct Splay { int mn[M],mx[M],v[M],Mn[M],L[M],R[M]; int fa[M],ch[M][2],siz[M],rt,tot; Splay() { v[0]=Mn[0]=mn[0]=L[0]=R[0]=inf; tot = 0; } void update(int u) { int ls = ch[u][0],rs = ch[u][1]; siz[u] = siz[ls]+siz[rs]+1; mn[u]=min(min(mn[ls],mn[rs]),v[u]); mx[u]=max(max(mx[ls],mx[rs]),v[u]); Mn[u]=inf; if(ls)Mn[u] = min(Mn[u],min(Mn[ls],abs(v[u]-R[ls]))); if(rs)Mn[u] = min(Mn[u],min(Mn[rs],abs(v[u]-L[rs]))); if(ls)L[u] = L[ls]; else L[u]=v[u]; if(rs)R[u] = R[rs]; else R[u]=v[u]; } void rotate(int x) { int y = fa[x],z = fa[y],k = (ch[y][1]==x); ch[y][k]=ch[x][!k],fa[ch[x][!k]]=y; ch[x][!k]=y,fa[y]=x; ch[z][ch[z][1]==y]=x,fa[x]=z; update(y),update(x); } void splay(int x,int goal) { while(fa[x]!=goal) { int y = fa[x],z = fa[y]; if(z!=goal) (ch[y][1]==x)^(ch[z][1]==y)?rotate(x):rotate(y); rotate(x); } if(!goal)rt=x; } int build(int l,int r,int f) { if(l>r)return 0; int mid = (l+r)>>1; int x = ++tot; fa[x]=f; L[x]=R[x]=v[x]=e[mid]; Mn[x]=inf; ch[x][0]=build(l,mid-1,x); ch[x][1]=build(mid+1,r,x); update(x); return x; } int get_pnt(int x,int k) { int tmp = siz[ch[x][0]]; if(k<=tmp)return get_pnt(ch[x][0],k); else if(k==tmp+1)return x; else return get_pnt(ch[x][1],k-1-tmp); } void Merge(int x,int d) { int x1 = get_pnt(rt,x); int x2 = get_pnt(rt,x+3); splay(x1,0);splay(x2,x1); x = ++tot; siz[x] = 1; fa[x] = x2;ch[x2][0] = x; v[x] = mn[x] = mx[x] = L[x] = R[x] = d; Mn[x] = inf; update(x2),update(x1); } void Insert(int x,int d) { int x1 = get_pnt(rt,x+1); int x2 = get_pnt(rt,x+2); splay(x1,0);splay(x2,x1); x = ++tot; siz[x] = 1; fa[x] = x2;ch[x2][0] = x; v[x] = mn[x] = mx[x] = L[x] = R[x] = d; Mn[x] = inf; update(x2),update(x1); } int Max(int x,int y) { x = get_pnt(rt,x); y = get_pnt(rt,y+2); splay(x,0);splay(y,x); return mx[ch[y][0]]-mn[ch[y][0]]; } int Min(int x,int y) { x = get_pnt(rt,x); y = get_pnt(rt,y+2); splay(x,0);splay(y,x); return Mn[ch[y][0]]; } }tr; char opt[10]; int main() { n=rd(),m=rd(); e[1]=e[n+2]=inf; for(int i=2;i<=n+1;i++)e[i]=rd(); tr.rt = tr.build(1,n+2,0); for(int x,y,i=1;i<=m;i++) { scanf("%s",opt+1); x = rd(),y = rd(); if(opt[2]=='e') { tr.Merge(x,y); }else if(opt[2]=='n') { tr.Insert(x,y); }else if(opt[2]=='a') { printf("%d ",tr.Max(x,y)); }else { printf("%d ",tr.Min(x,y)); } } // puts(""); return 0; }