思路
这里的初始化就不讲了,看完操作讲解就应该明白了，再不行就去看代码
对于操作1
由于操作2的需要，vector[n]存下数
对于操作2的维护
查询相邻两个元素的之间差值（绝对值）的最小值
先把所有答案存入一个小头堆里
比如 a,c之间你要插入b
那么，你就要删除|c-a|,然后加入|a-b|,|c-b|
之后的堆顶就是ans啦
对于支持删除的小头堆，我只会fhqtreap代替
但我也不想写, 因为太麻烦了
那么，我们能不能用STL自带的priority_queue
当然是可行的
维护两个堆，x，y
ans存入x中，需要删除的存入y中
每次更改的时候，改存的放入x，改删的放入y
每当x.top()==y.top()，就一起删掉，(注意!y.empty())
对于操作3的维护
查询所有元素中最接近的两个元素的差值（绝对值）
每次修改一个数，对最优答案都不会有坏的影响(显然)
那好的影响是啥
就是他和她的前驱，后继的差(显然)
注意前驱，后继的存在性
错误及其优化
最近老是不动脑子了(或者根本没脑子？)
insert操作查找前驱后继的时候可以省去find操作
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int maxn=5e5+7;
const int inf=0x3f3f3f3f;
inline int read() {
int x=0,f=1;char s=getchar();
for(; s>'9'||s<'0'; s=getchar()) if(s=='-') f=-1;
for(; s>='0'&&s<='9'; s=getchar()) x=x*10+s-'0';
return x*f;
}
int n,m,rt,ans2=inf,a[maxn],cnt;
struct node {
int ch[2],val,fa,siz;
} e[maxn*2];
vector<int> x[maxn];
priority_queue<int, vector<int>, greater<int> > ans1,delet;
inline int abs(int a) {return a>0?a:-a;}
inline void pushup(int x) {e[x].siz=e[e[x].ch[0]].siz+e[e[x].ch[1]].siz+1;}
inline void rotate(int x) {
int y=e[x].fa,z=e[y].fa,k=e[y].ch[1]==x;
e[x].fa=z;
e[z].ch[e[z].ch[1]==y]=x;
e[y].ch[k]=e[x].ch[k^1];
e[e[x].ch[k^1]].fa=y;
e[y].fa=x;
e[x].ch[k^1]=y;
pushup(x);pushup(y);
}
void splay(int x,int goal) {
while(e[x].fa!=goal) {
int y=e[x].fa,z=e[y].fa;
if(z!=goal)(e[y].ch[1]==x)^(e[z].ch[1]==y) ? rotate(y):rotate(x);
rotate(x);
}
if(!goal) rt=x;
}
void find(int a) {
int now=rt;
while(e[now].ch[e[now].val<a]&&e[now].val!=a)
now=e[now].ch[e[now].val<a];
splay(now,0);
}
void insert(int x) {
int now=rt,fa=0;
while(now&&e[now].val!=x)
fa=now,now=e[now].ch[e[now].val<x];
now=++cnt;
if(fa) e[fa].ch[e[fa].val<x]=now;
e[now].val=x;
e[now].fa=fa;
e[now].siz=1;
splay(now,0);
}
inline int qq(int x) {
if(e[rt].val<x) return rt;
int now=e[rt].ch[0];
while(e[now].ch[1]) now=e[now].ch[1];
return now;
}
inline int hj(int x) {
if(e[rt].val>x) return rt;
int now=e[rt].ch[1];
while(e[now].ch[0]) now=e[now].ch[0];
return now;
}
int build(int l,int r,int fa) {
if(l>r) return 0;
int mid=(l+r)>>1,p=++cnt;
e[p].val=a[mid];
e[p].fa=fa;
e[p].siz=1;
e[p].ch[0]=build(l,mid-1,p);
e[p].ch[1]=build(mid+1,r,p);
pushup(p);
return p;
}
int main() {
n=read(),m=read();
FOR(i,1,n) a[i]=read(),x[i].push_back(a[i]);
//ans1
FOR(i,2,n) ans1.push(abs(x[i][0]-x[i-1][0]));
//ans2
sort(a+1,a+1+n);
FOR(i,2,n) ans2=min(abs(a[i]-a[i-1]),ans2);
a[0]=-inf,a[n+1]=inf;
rt=build(0,n+1,0);
char s[10];
FOR(i,1,m) {
scanf("%s",s);
if(s[4]=='R') {
int a=read(),b=read();
//ans1
if(a!=n) delet.push(abs(x[a][x[a].size()-1]-x[a+1][0]));
x[a].push_back(b);
if(a!=n) ans1.push(abs(x[a][x[a].size()-1]-x[a+1][0]));
ans1.push(abs(x[a][x[a].size()-1]-x[a][x[a].size()-2]));
while(delet.size()&&ans1.top()==delet.top()) ans1.pop(),delet.pop();
//ans2
find(b);
if(e[rt].val==b) {ans2=0;continue;}
insert(b);
int x=e[qq(b)].val,y=e[hj(b)].val;
ans2=min(ans2,min(abs(x-b),abs(y-b)));
} else if(s[4]=='G') {
cout<<ans1.top()<<"
";
} else if(s[4]=='S') {
cout<<ans2<<"
";
}
}
return 0;
}