Description
21ZZ 年，冬。
小诚退休以后， 不知为何重新燃起了对物理学的兴趣。 他从研究所借了些实验仪器，整天研究各种微观粒子。这
一天， 小诚刚从研究所得到了一块奇异的陨石样本， 便迫不及待地开始观测。 在精密仪器的视野下，构成陨石
的每个原子都无比清晰。 小诚发现， 这些原子排成若干列， 每一列的结构具有高度相似性。于是，他决定对单
独一列原子进行测量和测试。被选中的这列共有 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 的子区间。
小诚坚信这项研究可以获得诺贝尔物理学奖。为了让小诚早日了结心愿，你能否帮助他实现上述的观测和测量呢？
Input
第一行， 两个整数 N， M， 分别表示最初的原子数目和事件总数。
第二行， N 个整数 E1, E2, …, EN， 由空格隔开。依次表示每个原子的能量。
接下来 M 行， 每行为一个字符串和两个整数， 描述一次事件，格式见题目描述。
N<=100,000,M<=100,000
1 ≤ e, Ei ≤ 109。 设 N’ 为当前时刻原子数目。
对于 merge 类事件， 1 ≤ x ≤ N’-1；
对于 insert 类事件， 1 ≤ x ≤ N’；
对于 max 和 min 类事件， 1 ≤ x < y ≤ N’。
任何时刻，保证 N’ ≥ 2。
Output
输出若干行， 按顺序依次表示每次 max 和 min 类事件的测量结果。
Sample Input
4 3
5 8 10 2
max 1 3
min 1 3
max 2 4
Sample Output
5 2 8
题目分析
区间最大极差就是最大值-最小值
区间最小极差就是最小的 每相邻的两个数的差
那么用非旋转treap维护一下就好了
维护区间最大值最小值 最小极差
因为有区间插入 合并 所以还要维护区间左端点的值 右端点的值
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int,int> par;
int n,m;
int val[101000*5],size[101000*5],lson[101000*5],rson[101000*5],key[101000*5];
int root,tot;
int maxx[101000*5],minn[101000*5],mi[101000*5],lval[101000*5],rval[101000*5];
void update(int x)
{
size[x]=size[lson[x]]+size[rson[x]]+1;
lval[x]=(lson[x]==0)?val[x]:lval[lson[x]];
rval[x]=(rson[x]==0)?val[x]:rval[rson[x]];
maxx[x]=max(val[x],max(maxx[lson[x]],maxx[rson[x]]));
minn[x]=val[x];
if(lson[x]) minn[x]=min(minn[x],minn[lson[x]]);
if(rson[x]) minn[x]=min(minn[x],minn[rson[x]]);
mi[x]=1<<30;
if(lson[x]) mi[x]=min(mi[x],abs(val[x]-rval[lson[x]])),mi[x]=min(mi[x],mi[lson[x]]);
if(rson[x]) mi[x]=min(mi[x],abs(val[x]-lval[rson[x]])),mi[x]=min(mi[x],mi[rson[x]]);
}
void pushdown(int x)
{
return ;
}
int merge(int x,int y)
{
if(x==0||y==0) return x|y;
pushdown(x),pushdown(y);
if(key[x]<key[y])
{
lson[y]=merge(x,lson[y]),update(y);
return y;
}
rson[x]=merge(rson[x],y),update(x);
return x;
}
par split(int x,int k)
{
if(k==0) return make_pair(0,x);
pushdown(x);
int l=lson[x],r=rson[x];
if(k==size[lson[x]])
{
lson[x]=0,update(x);
return make_pair(l,x);
}
if(k==size[lson[x]]+1)
{
rson[x]=0,update(x);
return make_pair(x,r);
}
par t;
if(k<size[lson[x]])
{
t=split(l,k);
lson[x]=t.second,update(x);
return make_pair(t.first,x);
}
else
{
t=split(r,k-size[lson[x]]-1);
rson[x]=t.first,update(x);
return make_pair(x,t.second);
}
}
char s[10];
int main()
{
scanf("%d%d",&n,&m);
for(int x,i=1;i<=n;i++)
{
scanf("%d",&val[++tot]);
maxx[tot]=val[i],minn[tot]=val[i];
lval[tot]=val[i],rval[tot]=val[i];
mi[tot]=1<<30;
size[tot]=1,key[tot]=rand(),root=merge(root,tot);
}
for(int x,y,i=1;i<=m;i++)
{
scanf("%s%d%d",&s[0],&x,&y);
if(s[1]=='e')
{
par t1,t2;
t2=split(root,x+1);
t1=split(t2.first,x-1);
size[++tot]=1,key[tot]=rand();
lval[tot]=rval[tot]=val[tot]=maxx[tot]=minn[tot]=y,mi[tot]=1<<30;
root=merge(merge(t1.first,tot),t2.second);
}
else if(s[0]=='i')
{
par t1,t2;
t1=split(root,x);
size[++tot]=1,key[tot]=rand();
lval[tot]=rval[tot]=val[tot]=maxx[tot]=minn[tot]=y,mi[tot]=1<<30;
root=merge(merge(t1.first,tot),t1.second);
}
else if(s[1]=='i')
{
par t1,t2;
t2=split(root,y);
t1=split(t2.first,x-1);
printf("%d\n",mi[t1.second]);
root=merge(merge(t1.first,t1.second),t2.second);
}
else if(s[1]=='a')
{
par t1,t2;
t2=split(root,y);
t1=split(t2.first,x-1);
printf("%d\n",maxx[t1.second]-minn[t1.second]);
root=merge(merge(t1.first,t1.second),t2.second);
}
}
return 0;
}
