一眼看过去想着可以不用splay，采用数据离散化的动态开点线段树和multiset来写。跑出来最开始没有离散化最后一个样例me了，离散化之后全wa了，样例一自己本机跑出来答案一样的，为啥洛谷上过不了。最后有样例一及其答案，可以复制代码跑一下。

#include<bits/stdc++.h>
#define ll long long 
//#define int long long
#define endl "\n"
#define FAST std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int inf = 0x3f3f3f3f;
using namespace std;
struct node{
	int l,r,sum;
	int mx,mn;
	int son[2];
}tree[6000010];
int n,m,tot,root;
void update(int &id,int l,int r,int st){
	if(id==0){
		id=++tot;
		tree[id].l=l,tree[id].r=r;
		tree[id].mx=-inf,tree[id].mn=inf;
		tree[id].sum=0;
	}
	tree[id].sum++;
	if(l==r){
		tree[id].mx=tree[id].mn=l;
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=st)update(tree[id].son[0],l,mid,st);
	else update(tree[id].son[1],mid+1,r,st);
	if(tree[id].son[0]==0){
		tree[id].mx=tree[tree[id].son[1]].mx;
		tree[id].mn=tree[tree[id].son[1]].mn;
	}
	else if(tree[id].son[1]==0){
		tree[id].mx=tree[tree[id].son[0]].mx;
		tree[id].mn=tree[tree[id].son[0]].mn;
	}
	else{
		tree[id].mx=max(tree[tree[id].son[0]].mx,tree[tree[id].son[1]].mx);
		tree[id].mn=min(tree[tree[id].son[0]].mn,tree[tree[id].son[1]].mn);
	}
}
int query(int id,int l,int r,int type){
	if(type==1){//取极大值 
		if(id==0)return -inf;
		else if(tree[id].l>=l&&tree[id].r<=r)return tree[id].mx;
		else {
			int mid=(tree[id].l+tree[id].r)>>1;
			if(mid>=r)return query(tree[id].son[0],l,r,1);
			else if(mid<l)return query(tree[id].son[1],l,r,1);
			else return max(query(tree[id].son[0],l,r,1),query(tree[id].son[1],l,r,1));
		}
	}
	else{
		if(id==0)return inf;
		else if(tree[id].l>=l&&tree[id].r<=r)return tree[id].mn;
		else{
			int mid=(tree[id].l+tree[id].r)>>1;
			if(mid>=r)return query(tree[id].son[0],l,r,2);
			else if(mid<l)return query(tree[id].son[1],l,r,2);
			else return min(query(tree[id].son[0],l,r,2),query(tree[id].son[1],l,r,2));
		}
	}
}
vector<int>vec[500010];
multiset<int>st;
string s[500010];
int b[1000010],lk[500010][2],cnt;
int get_id(int x){
	return lower_bound(b+1,b+cnt+1,x)-b; 
}
signed main(){
	FAST
	int ans=inf;
	cnt=0;
	cin>>n>>m;
	for(int i=1,k;i<=n;i++){
		cin>>k;
		b[++cnt]=k;
		vec[i].push_back(k);
		//cout<<ans<<endl;
	}
	for(int i=2;i<=n;i++){
		st.insert(abs(vec[i][0]-vec[i-1][0]));
	}
	getline(cin,s[0]);
	for(int i=1;i<=m;i++){
		getline(cin,s[i]);
		if(s[i][0]=='I'){
			int sum=0;
			for(int j=7;j<s[i].length();j++){
				if(s[i][j]==' '){
					lk[i][0]=sum;
					sum=0;
				}
				else{
					sum=sum*10+s[i][j]-'0';
				}
			}
			b[++cnt]=sum;
			lk[i][1]=sum;
		}
	}
	sort(b+1,b+cnt+1);
	cnt=unique(b+1,b+cnt+1)-b-1;
//	for(int i=1;i<=cnt;i++)cout<<b[i]<<" ";
//	cout<<endl;
	for(int i=1,k;i<=n;i++){
		k=get_id(vec[i][0]);
		//cout<<"k: "<<k<<endl;
		int tt;
		tt=query(root,1,k,1);
		if(tt!=-inf)ans=min(ans,b[k]-b[tt]);
		tt=query(root,k,cnt,2);
		if(tt!=inf)ans=min(ans,b[tt]-b[k]);
		update(root,1,cnt,k);
		//cout<<"* "<<ans<<endl;
	}
	for(int i=1;i<=m;i++){
		int x,y;
		if(s[i][0]=='I'){
			x=lk[i][0],y=get_id(lk[i][1]);
			if(x<n){
				st.erase(st.find(abs(vec[x+1][0]-vec[x][vec[x].size()-1])));
				st.insert(abs(vec[x+1][0]-b[y]));
			}
			st.insert(abs(b[y]-vec[x][vec[x].size()-1]));
			vec[x].push_back(b[y]);
			int tt;
			tt=query(root,1,y,1);
			if(tt!=-inf)ans=min(ans,b[y]-b[tt]);
			tt=query(root,y,cnt,2);
			if(tt!=inf)ans=min(ans,b[tt]-b[y]);
			update(root,1,cnt,y);
		}
		else if(s[i][4]=='G'){
			auto it=st.begin();
			cout<<*it<<endl;
		}
		else cout<<ans<<endl;
	}
}

样例一

10 20
33 87024675 43512354 174049319 217561644 130536998 261073969 348098617 304586294 391610940
INSERT 1 21770567
INSERT 2 174060039
INSERT 2 43514251
MIN_GAP
INSERT 2 174060043
INSERT 2 65272338
MIN_SORT_GAP
INSERT 6 152314558
INSERT 6 261101532
MIN_GAP
INSERT 6 152314554
MIN_GAP
MIN_GAP
INSERT 1 152315265
MIN_GAP
INSERT 2 152299949
MIN_SORT_GAP
MIN_GAP
INSERT 8 435123234
INSERT 5 174083729

答案(这就是洛谷给的正确答案)

1897
4
27563
21759984
21759984
21759984
4
21770534