https://www.lydsy.com/JudgeOnline/problem.php?id=1058
https://www.luogu.org/problemnew/show/P1110#sub
显然这三种操作都可以splay做啊，愉快的敲了两个splay……
T！L！E！
（总觉得复杂度是对的，可能改成边插边更新（就像本代码一样）能过）
第三种操作没啥好想法，考虑第二种操作，用线段树维护差值最小值。
插入的元素对后来插这个位置的元素造成的贡献有影响，但之后将永远不会改变，于是暴力更新这个差值。
插入的元素影响了它之后位置的元素的贡献，且会不断改变，于是在线段树更新这个差值即可。
#include<cstdio>
#include<queue>
#include<cctype>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=;
const int INF=1e9;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
char s[];
int fa[N],tr[N][],key[N],id[N];
int b[N],del[N],c[N];
int root,sz;
inline bool get(int x){
return tr[fa[x]][]==x;
}
int pre(){
int now=tr[root][];
while(tr[now][])now=tr[now][];
return now;
}
int nxt(){
int now=tr[root][];
while(tr[now][])now=tr[now][];
return now;
}
inline void rotate(int x){
int y=fa[x],z=fa[y],which=get(x);
tr[y][which]=tr[x][which^];fa[tr[y][which]]=y;
fa[y]=x;tr[x][which^]=y;fa[x]=z;
if(z)tr[z][tr[z][]==y]=x;
return;
}
inline void splay(int x){
int f=fa[x];
while(f){
if(fa[f])rotate(get(x)==get(f)?f:x);
rotate(x);f=fa[x];
}
root=x;
return;
}
inline void insert(int v){
if(!root){
sz++;tr[sz][]=tr[sz][]=fa[sz]=;
key[sz]=v;root=sz;
return;
}
int now=root,f=;
while(){
f=now;
now=tr[now][key[now]<=v];
if(!now){
sz++;tr[sz][]=tr[sz][]=;
fa[sz]=f;key[sz]=v;
tr[f][key[f]<=v]=sz;
splay(sz);
break;
}
}
return;
}
void build(int a,int l,int r){
if(l==r){
del[a]=abs(b[l]-b[l-]);
return;
}
int mid=(l+r)>>;
build(a*,l,mid);build(a*+,mid+,r);
del[a]=min(del[a*],del[a*+]);
}
void ins(int a,int l,int r,int p,int x){
if(l==r){
del[a]=x;
return;
}
int mid=(l+r)>>;
if(p<=mid)ins(a*,l,mid,p,x);
else ins(a*+,mid+,r,p,x);
del[a]=min(del[a*],del[a*+]);
}
int main(){
int n=read(),m=read();
int ans1=INF,ans2=INF;
b[]=c[]=INF;
for(int i=;i<=n;i++){
b[i]=c[i]=read();
insert(b[i]);
if(i!=){
int pr=pre(),nx=nxt();
if(pr)ans2=min(ans2,abs(key[pr]-b[i]));
if(nx)ans2=min(ans2,abs(key[nx]-b[i]));
}
}
build(,,n);
for(int i=;i<=m;i++){
scanf("%s",s);
if(s[]=='I'){
int pos=read(),v=read();
insert(v);
int pr=pre(),nx=nxt();
if(pr)ans2=min(ans2,abs(key[pr]-v));
if(nx)ans2=min(ans2,abs(key[nx]-v));
ans1=min(ans1,abs(c[pos]-v));
c[pos]=v;
if(pos+<=n)ins(,,n,pos+,abs(b[pos+]-v));
}else if(strlen(s)==){
printf("%d\n",min(del[],ans1));
}else{
printf("%d\n",ans2);
}
}
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++