链接：Yet another range difference query!。

做法是离线询问离散化，建立以离散化的权值为下标的维护离散化前的权值与其前驱的差分值的区间最小值的权值线段树，然后用平衡树维护前驱后继，顺便支持一个查 $K$-th element 来找到询问在线段树上对应的区间。

已经调了 4h+ 了，实在无法只能求助。感谢。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {
	ll x=0,f=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch&15),ch=getchar();
	return f?-x:x;
}
const int N=5000100,inf=1e9+7; int tot,root;
struct Qry { char t; int l,r; } qy[N],lqy[N]; int qt,T;
struct node { int l,r,sz,key,val; } tr[N]; int mp[N];
int crtnd(int val) { tr[++tot]={0,0,1,rand(),val}; return tot; }
void update(int now) { tr[now].sz=tr[tr[now].l].sz+tr[tr[now].r].sz+1; }
void split(int now,int v,int &x,int &y) {
	if(!now) return x=y=0,void();
	if(tr[now].val<=v) x=now,split(tr[now].r,v,tr[now].r,y),update(x);
	else y=now,split(tr[now].l,v,x,tr[now].l),update(y);
}
int merge(int x,int y) {
	if(!x||!y) return x+y;
	if(tr[x].key>tr[y].key) return tr[x].r=merge(tr[x].r,y),update(x),x;
	else return tr[y].l=merge(x,tr[y].l),update(y),y;
}
int rt0,rt1,rt2;
void ins(int x) { split(root,x,rt0,rt1),root=merge(merge(rt0,crtnd(x)),rt1); }
void del(int x) { split(root,x,rt0,rt1),split(rt0,x-1,rt0,rt2),rt2=merge(tr[rt2].l,tr[rt2].r),root=merge(merge(rt0,rt2),rt1); }
int Pre(int x) {
	split(root,x-1,rt0,rt1);
	int now=rt0;
	while(tr[now].r) now=tr[now].r;
	int res=now?tr[now].val:-1;
	root=merge(rt0,rt1);
	return res;
}
int Nxt(int x) {
	split(root,x,rt0,rt1);
	int now=rt1;
	while(tr[now].l) now=tr[now].l;
	int res=now?tr[now].val:-1;
	root=merge(rt0,rt1);
	return res;
}
int Kth(int x) {
	int now=root;
	while(now) {
		if(tr[tr[now].l].sz+1==x) break;
		if(tr[tr[now].l].sz<x) x-=tr[tr[now].l].sz+1,now=tr[now].r;
		else now=tr[now].l;
	}
	return tr[now].val;
}
void Output(int now) {
	if(!now) return;
	Output(tr[now].l);
	printf("[%d %d]\n",tr[now].val,mp[tr[now].val]);
	Output(tr[now].r);
}
int extr[N*4];
void exins(int l,int r,int now,int x,int y) {
	if(l==r) return extr[now]=y,void();
	int mid=(l+r)>>1;
	if(mid>=x) exins(l,mid,now<<1,x,y);
	else exins(mid+1,r,now<<1|1,x,y);
	extr[now]=min(extr[now<<1],extr[now<<1|1]);
}
int find(int l,int r,int now,int x,int y) {
	if(l>y||r<x) return inf;
	if(l>=x&&r<=y) return extr[now];
	int mid=(l+r)>>1;
	return min(find(l,mid,now<<1,x,y),find(mid+1,r,now<<1|1,x,y));
}
int Abs(int x) { return x<0?-x:x; }
signed main() {
	srand((unsigned)time(NULL));
	vector<int> pri;
	for(int Case=read(); Case; --Case) {
		char ch=getchar(); while(ch!='I'&&ch!='D'&&ch!='N'&&ch!='X') ch=getchar();
		if(ch=='I'||ch=='D') qy[++qt]={ch,read(),-1},pri.push_back(qy[qt].l);
		else qy[++qt]={ch,read()+1,read()+1}; lqy[qt]=qy[qt];
	}
	function<void(int,int,int)> build=[&](int l,int r,int now) {
		if(l==r) return extr[now]=inf,void();
		int mid=(l+r)>>1;
		build(l,mid,now<<1),build(mid+1,r,now<<1|1);
	};
	sort(pri.begin(),pri.end()),pri.erase(unique(pri.begin(),pri.end()),pri.end()),T=pri.size();
	for(int i=1; i<=qt; ++i) (lqy[i].t=='I'||lqy[i].t=='D')&&(lqy[i].l=lower_bound(pri.begin(),pri.end(),lqy[i].l)-pri.begin()+1);
	for(int i=1; i<=qt; ++i) (lqy[i].t=='I'||lqy[i].t=='D')&&(mp[lqy[i].l]=qy[i].l); build(1,T,1);
	for(int i=1,l,r; i<=qt; ++i) {
		if(lqy[i].t=='N'||lqy[i].t=='X') l=Kth(lqy[i].l),r=Kth(lqy[i].r);
		if(lqy[i].t=='I') {
			split(root,lqy[i].l,rt0,rt1);
			split(rt0,lqy[i].l-1,rt0,rt2);
			if(tr[rt2].val==lqy[i].l) { root=merge(merge(rt0,rt2),rt1); continue; }
			root=merge(merge(rt0,rt2),rt1);
			ins(lqy[i].l); int tmp=Nxt(lqy[i].l),pmt=Pre(lqy[i].l);
			if(~pmt) exins(1,T,1,lqy[i].l,Abs(qy[i].l-mp[pmt]));
			else exins(1,T,1,lqy[i].l,inf);
			if(~tmp) exins(1,T,1,tmp,Abs(mp[tmp]-qy[i].l));
		}
		else if(lqy[i].t=='D') {
			split(root,lqy[i].l,rt0,rt1);
			split(rt0,lqy[i].l-1,rt0,rt2);
			if(tr[rt2].val!=lqy[i].l) { root=merge(merge(rt0,rt2),rt1); continue; }
			root=merge(merge(rt0,rt2),rt1);
			del(lqy[i].l); int tmp=Nxt(lqy[i].l),pmt=Pre(lqy[i].l);
			exins(1,T,1,lqy[i].l,inf);
			if(~tmp)
				if(~pmt) exins(1,T,1,tmp,Abs(mp[tmp]-mp[pmt]));
				else exins(1,T,1,tmp,inf);
		}
		else if(lqy[i].t=='N') printf("%d\n",l==r?-1:find(1,T,1,l+1,r));
		else printf("%d\n",l==r?-1:Abs(mp[l]-mp[r]));
	}
	return 0;
}