傻逼题……区间最小极差一定是相邻的两个元素所构成的
然后就维护一下区间最大最小值，最小极差，splay随便搞搞就行了
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<iomanip> #include<cstring> #include<cmath> #include<ctime> #include<vector> #include<stack> #include<queue> #include<set> #include<bitset> #include<map> using namespace std; #define MAXN 200010 #define MAXM 10010 #define INF 1000000000 #define MOD 1000000007 #define ll long long #define eps 1e-8 #define tr son[son[rt][1]][0] int fa[MAXN],son[MAXN][2],mn[MAXN],mx[MAXN],lv[MAXN],rv[MAXN],siz[MAXN],mnv[MAXN],v[MAXN]; int rt,tot; int n,m; inline void ud(int x){ siz[x]=siz[son[x][0]]+siz[son[x][1]]+1; mn[x]=mx[x]=lv[x]=rv[x]=v[x]; mnv[x]=INF; if(son[x][0]){ mn[x]=min(mn[x],mn[son[x][0]]); mx[x]=max(mx[x],mx[son[x][0]]); mnv[x]=min(mnv[x],min(mnv[son[x][0]],abs(v[x]-rv[son[x][0]]))); lv[x]=lv[son[x][0]]; } if(son[x][1]){ mn[x]=min(mn[x],mn[son[x][1]]); mx[x]=max(mx[x],mx[son[x][1]]); mnv[x]=min(mnv[x],min(mnv[son[x][1]],abs(v[x]-lv[son[x][1]]))); rv[x]=rv[son[x][1]]; } } inline void cot(int x,int y,bool z){ if(x){ fa[x]=y; } if(y){ son[y][z]=x; } } inline void rot(int x,bool z){ int xx=fa[x],xxx=fa[xx]; cot(son[x][z],xx,z^1); cot(x,xxx,son[xxx][1]==xx); cot(xx,x,z); ud(xx); } void splay(int x,int y){ int xx=fa[x],xxx=fa[xx]; while(xx!=y){ if(xxx==y){ rot(x,son[xx][0]==x); }else{ bool z=son[xxx][0]==xx; if(son[xx][z]==x){ rot(x,z^1); rot(x,z); }else{ rot(xx,z); rot(x,z); } } xx=fa[x],xxx=fa[xx]; } ud(x); if(!y){ rt=x; } } int find(int x,int y){ if(siz[son[x][0]]+1==y){ return x; } if(y<=siz[son[x][0]]){ return find(son[x][0],y); }else{ return find(son[x][1],y-siz[son[x][0]]-1); } } inline void pick(int x,int y){ splay(find(rt,x),0); splay(find(rt,y+2),rt); } inline void UD(){ ud(son[rt][1]); ud(rt); } void ins(int x){ tr=++tot; v[tr]=x; ud(tr); fa[tr]=son[rt][1]; UD(); } int main(){ int i,x,y; char o[10]; scanf("%d%d",&n,&m); rt=++tot; son[rt][1]=++tot; fa[tot]=1; UD(); for(i=0;i<n;i++){ scanf("%d",&x); pick(i+1,i); ins(x); } while(m--){ scanf("%s%d%d",o,&x,&y); if(o[1]=='e'){ pick(x,x+1); ins(y); } if(o[1]=='n'){ pick(x+1,x); ins(y); } if(o[1]=='a'){ pick(x,y); printf("%d\n",mx[tr]-mn[tr]); } if(o[1]=='i'){ pick(x,y); printf("%d\n",mnv[tr]); } } return 0; } /* 4 3 5 8 10 2 max 1 3 min 1 3 max 2 4 */
