首先merge就是先delete两次再insert，Max就是整个区间的最大值减最小值，Min就是区间中所有相邻两数差的最小值。
Splay支持区间最大值，区间最小值，区间相邻差最小值即可。
1 #include2 #include 3 #include 4 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 5 using namespace std; 6 7 const int N=200010,inf=1e9; 8 char op[10]; 9 int n,m,nd,rt,x,y,v[N],d[N],sz[N],mx[N],mn[N],mnd[N],a[N],ch[N][2],f[N];10 11 int Abs(int x){ return x<0 ? -x : x; }12 13 void upd(int x){14 int ls=ch[x][0],rs=ch[x][1];15 sz[x]=sz[ls]+sz[rs]+1;16 mn[x]=min(v[x],min(mn[ls],mn[rs]));17 mx[x]=max(v[x],max(mx[ls],mx[rs]));18 mnd[x]=min(d[x],min(mnd[ls],mnd[rs]));19 }20 21 void rot(int &rt,int x){22 int y=f[x],z=f[y],w=ch[y][1]==x;23 if (y==rt) rt=x; else ch[z][ch[z][1]==y]=x;24 f[y]=x; f[x]=z; f[ch[x][w^1]]=y;25 ch[y][w]=ch[x][w^1]; ch[x][w^1]=y; upd(y);26 }27 28 void splay(int &rt,int x){29 while (x!=rt){30 int y=f[x],z=f[y];31 if (y!=rt) (ch[z][1]==y ^ ch[y][1]==x) ? rot(rt,x) : rot(rt,y);32 rot(rt,x);33 }34 upd(x);35 }36 37 int build(int l,int r){38 if (l>r) return 0;39 int x=++nd,mid=(l+r)>>1;40 v[x]=a[mid]; d[x]=Abs(a[mid]-a[mid-1]); sz[x]=1;41 f[ch[x][0]=build(l,mid-1)]=x; f[ch[x][1]=build(mid+1,r)]=x;42 upd(x); return x;43 }44 45 int find(int x,int k){46 if (sz[ch[x][0]]+1==k) return x;47 if (k<=sz[ch[x][0]]) return find(ch[x][0],k);48 else return find(ch[x][1],k-sz[ch[x][0]]-1);49 }50 51 void ins(int p,int k){52 int x=find(rt,p+1),y=find(rt,p+2);53 splay(rt,x); splay(ch[x][1],y);54 v[++nd]=k; d[nd]=Abs(v[nd]-v[x]); f[nd]=y; sz[nd]=1;55 ch[y][0]=nd; d[y]=Abs(v[y]-v[nd]); upd(nd); upd(y); upd(x);56 }57 58 void del(int p){59 int x=find(rt,p),y=find(rt,p+2);60 splay(rt,x); splay(ch[x][1],y);61 ch[y][0]=0; d[y]=Abs(v[y]-v[x]); upd(y); upd(x);62 }63 64 int que(int l,int r,int op){65 int x=find(rt,l),y=find(rt,r+2);66 splay(rt,x); splay(ch[x][1],y);67 return op==0 ? mx[ch[y][0]] : (op==1 ? mn[ch[y][0]] : mnd[ch[y][0]]);68 }69 70 int main(){71 freopen("bzoj4864.in","r",stdin);72 freopen("bzoj4864.out","w",stdout);73 scanf("%d%d",&n,&m); mnd[0]=mn[0]=inf;74 rep(i,1,n) scanf("%d",&a[i]);75 rt=build(0,n+1);76 rep(i,1,m){77 scanf("%s%d%d",op,&x,&y);78 if (op[1]=='e') del(x),del(x),ins(x-1,y);79 if (op[1]=='n') ins(x,y);80 if (op[1]=='a') printf("%d\n",que(x,y,0)-que(x,y,1));81 if (op[1]=='i') printf("%d\n",que(x+1,y,2));82 }83 return 0;84 }