Description
给出一个长度为n的序列，第i个数为a，进行以下四种操作：
merge x e：将当前第x个数和第x+1个数合并，得到一个新的数e；
insert x e：在当前第x个数和第x+1个数之间插入一个新的数e；
max x y：求当前第x个数到第y个数之间任意子区间中区间极差的最大值;
min x y：求当前第x个数到第y个数之间任意子区间中区间极差的最小值
（区间极差：区间内最大值与最小值之差）
（子区间长度至少为2）
Solution
splay模板题。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,a[];
namespace splay{
#define lson(x) t[x].lc
#define rson(x) t[x].rc
#define fa(x) t[x].fa
struct tree{
int lc,rc,fa;
int size,val,maxn,minn;
int delta,ans;
}t[]={};
int root=,cnt=;
void pushup(int x){
t[x].size=t[lson(x)].size+t[rson(x)].size+;
t[x].maxn=max(t[x].val,max(t[lson(x)].maxn,t[rson(x)].maxn));
t[x].minn=t[x].val;
if(lson(x))
t[x].minn=min(t[x].minn,t[lson(x)].minn);
if(rson(x))
t[x].minn=min(t[x].minn,t[rson(x)].minn);
t[x].ans=t[x].delta;
if(lson(x))
t[x].ans=min(t[x].ans,t[lson(x)].ans);
if(rson(x))
t[x].ans=min(t[x].ans,t[rson(x)].ans);
return;
}
int build(int l,int r){
int mid=(l+r)>>,s=++cnt;
t[s].val=a[mid];
t[s].delta=(mid)?abs(a[mid]-a[mid-]):0x3f3f3f3f;
if(l<mid){
lson(s)=build(l,mid-);
fa(lson(s))=s;
}
if(mid<r){
rson(s)=build(mid+,r);
fa(rson(s))=s;
}
pushup(s);
return s;
}
int find(int k){
int p=root;
while(true){
if(t[lson(p)].size>=k)
p=lson(p);
else if(t[lson(p)].size+==k)
return p;
else{
k-=t[lson(p)].size+;
p=rson(p);
}
}
}
void rotate(int x){
int fa=fa(x);
if(fa==root)
root=x;
if(x==lson(fa)){
lson(fa)=rson(x);
fa(rson(x))=fa;
rson(x)=fa;
fa(x)=fa(fa);
if(root!=x){
if(fa==lson(fa(fa)))
lson(fa(fa))=x;
else
rson(fa(fa))=x;
}
fa(fa)=x;
}
else{
rson(fa)=lson(x);
fa(lson(x))=fa;
lson(x)=fa;
fa(x)=fa(fa);
if(root!=x){
if(fa==lson(fa(fa)))
lson(fa(fa))=x;
else
rson(fa(fa))=x;
}
fa(fa)=x;
}
pushup(fa);
pushup(x);
return;
}
void splay(int x,int y){
while(fa(x)!=y){
if(fa(fa(x))==y){
rotate(x);
return;
}
int a=(x==lson(fa(x)))?:-;
int b=(fa(x)==lson(fa(fa(x))))?:-;
if(a*b==){
rotate(fa(x));
rotate(x);
}
else{
rotate(x);
rotate(x);
}
}
return;
}
void insert(int x,int y){
splay(find(x),);
splay(find(x+),root);
lson(rson(root))=++cnt;
fa(cnt)=rson(root);
t[cnt].size=;
t[cnt].val=t[cnt].maxn=t[cnt].minn=y;
t[cnt].delta=t[cnt].ans=abs(t[root].val-y);
t[rson(root)].delta=abs(t[rson(root)].val-y);
pushup(rson(root));
pushup(root);
return;
}
void del(int x){
splay(find(x-),);
splay(find(x+),root);
lson(rson(root))=;
t[rson(root)].delta=abs(t[root].val-t[rson(root)].val);
pushup(rson(root));
pushup(root);
}
int querymaxn(int l,int r){
splay(find(l-),);
splay(find(r+),root);
return t[lson(rson(root))].maxn-t[lson(rson(root))].minn;
}
int queryminn(int l,int r){
splay(find(l-),);
splay(find(r+),root);
return t[lson(rson(root))].ans;
}
#undef lson
#undef rson
#undef fa
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",a+i);
a[]=0x3f3f3f3f;
a[n+]=-0x3f3f3f3f;
splay::root=splay::build(,n+);
scanf("%d",&m);
while(m--){
char op[];int x,y;
scanf("%s%d%d",op,&x,&y);
if(op[]=='i')
splay::insert(x+,y);
else if(op[]=='e'){
splay::del(x+);
splay::del(x+);
splay::insert(x,y);
}
else if(op[]=='a')
printf("%d\n",splay::querymaxn(x+,y+));
else
printf("%d\n",splay::queryminn(x+,y+));
}
return ;
}