[文章目录]
Description
被选中的这列共有 N 个顺序排列的原子。 最初， 第 i 个原子具有能量 Ei。 随着
时间推移和人为测试， 这列原子在观测上会产生两种变化：
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 的子区间。
小诚坚信这项研究可以获得诺贝尔物理学奖。为了让小诚早日了结心愿，你能否帮助他实现上述的观测和测量呢？
splay，然后区间最大极差，显然是区间的最大值-最小值。
最小极差，因为极差的定义说是一个区间的最大值-最小值，然后要求这个值最小，所以肯定只是两个元素的子区间更优。（包含更多的元素还不如少点），所以区间子区间最小极值就是这个区间每两个相邻的元素做差，取绝对值最小的那个。然后放到伸展树上，需要维护区间两边元素的值，区间最大小值，size，区间最小极值。
woc，一直PE，后来看出来样例不是标准的输出，哭死在BZ。另外指针版的splay一定要记得在加一个新的指针后将指针的fa更新一下，另外，switch（）要有break；
啊啊啊啊啊啊啊啊，指针啊，哭死。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m;
int a[101000];
char st[30];
int ABS(int x)
{return x<0?-x:x; }
int read()
{
char ch=getchar();int re=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re;
}
struct node
{
node *fa,*ls,*rs;
int val,mx,mi,mii,size;
int lval,rval;
node(int x);
node();
void push_up();
}*null=new node(),*root;
node :: node()
{
ls=rs=fa=null;
rval=val=lval=mi=mii=1<<30;
mx=-1<<30;
size=0;
}
node :: node(int x)
{
fa=ls=rs=null;
lval=rval=val=x;
mi=x;
mii=1<<30;
mx=x;
size=1;
}
void node :: push_up()
{
size=ls->size+rs->size+1;
lval=ls==null?val:ls->lval;
rval=rs==null?val:rs->rval;
mii=min(min(ABS(ls->rval-val),ABS(rs->lval-val)),min(rs->mii,ls->mii));
mx=max(val,max(ls->mx,rs->mx));
mi=min(val,min(ls->mi,rs->mi));
}
void zig(node *x)
{
node *y=x->fa;
y->ls=x->rs;
x->rs->fa=y;
x->rs=y;
x->fa=y->fa;
if(y==y->fa->ls) y->fa->ls=x;
else y->fa->rs=x;
y->fa=x;
y->push_up();
x->push_up();
if(y==root) root=x;
}
void zag(node *x)
{
node *y=x->fa;
y->rs=x->ls;
x->ls->fa=y;
x->ls=y;
x->fa=y->fa;
if(y==y->fa->ls) y->fa->ls=x;
else y->fa->rs=x;
y->fa=x;
y->push_up();
x->push_up();
if(y==root) root=x;
}
void splay(node *x,node *tar)
{
while(1)
{
node *y=x->fa,*z=y->fa;
if(y==tar) break;
if(z==tar)
{
if(x==y->ls) zig(x);
else zag(x);
break;
}
if(x==y->ls)
{
if(y==z->ls) zig(y);
zig(x);
}
else
{
if(y==z->rs) zag(y);
zag(x);
}
}
}
void find(node *x,int y,node *z)
{
while(1)
{
int tmp=x->ls->size;
if(y<=tmp) x=x->ls;
else
{
y-=tmp;
if(y==1) break;
y--;
x=x->rs;
}
}
splay(x,z);
}
node *build(int l,int r)
{
if(l>r) return null;
int mid=l+r>>1;
node *re=new node(a[mid]);
re->ls=build(l,mid-1);
re->rs=build(mid+1,r);
re->push_up();
re->ls->fa=re;
re->rs->fa=re;
return re;
}
void initialize()
{
root=new node();
root->rs=new node();
root->rs->ls=build(1,n);
root->rs->ls->fa=root->rs;
root->rs->fa=root;
root->rs->push_up();
root->push_up();
}
void Free(node *x)
{
if(x==null) return ;
Free(x->rs);
Free(x->ls);
free(x);
}
void del(int x)
{
Free(root->rs->ls);
root->rs->ls=new node(x);
root->rs->ls->fa=root->rs;
root->rs->push_up();
root->push_up();
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
a[i]=read();
initialize();
find(root,1,null);
int x,e;
while(m)
{
m--;
scanf("%s",st);
x=read();e=read();
switch(st[1])
{
case 'e':
{
find(root,x,null);
find(root,x+3,root);
del(e);
break;
}
case 'n':
{
find(root,x+1,null);
find(root,x+2,root);
root->rs->ls=new node(e);
root->rs->ls->fa=root->rs;
root->rs->push_up();
root->push_up();
break;
}
case 'a':
{
find(root,x,null);
find(root,e+2,root);
printf("%d\n",root->rs->ls->mx-root->rs->ls->mi);
break;
}
case 'i':
{
find(root,x,null);
find(root,e+2,root);
printf("%d\n",root->rs->ls->mii);
break;
}
}
}
return 0;
}