Lpz在做[P3204最小差值]的时候冥思苦想出了一种数据结构，它可以维护这样一个集合：能动态的插入，删除元素，还可以查询某个区间内的已插入的元素“最小差值”。最小差值就是一个集合内任意两个元素的差值的绝对值的最小值。可是在看了题解过后，Lpz真的很不服气，Mr_He给出的题解简直太巧妙了，谁想得到啊！可是Lpz发现，Mr_He的算法不能删除元素，当然也不能查询区间“最小差值”。于是面对这样一个“升级版”的最小差值，Lpz准备一展身手。但Lpz又觉得这个这个程序真的太难写了，于是，任务就交给你了！
【输入格式】
第一行有一个正整数M(1 <= M <= 200000)，接下来的M行内容为下面操作之一 1. Query x y 查询集合中落在区间[x,y]中的“最小差值” 2. Insert x 向你的集合中添加元素x（若x已存在则忽略） 3. Delete x 从你的集合中删除x（若x不存在则忽略）. (x,y均为整数)
【输出格式】
对于每个Query操作，如果存在最小差值，请输出它，否则输出-1. 对于每个Delete操作，如果集合中不存在x，你应当输出“Failed”并忽略该操作. 对于其他操作，你不需要输出任何东西. 每个输出占一行.
【输入样例】
6 Insert 2 Insert 4 Qeury 2 4 Delete 3 Delete 2 Query 1 10
【输出样例】
2 Failed -1
【数据范围】
对于30%的测试点 1 ≤ M ≤ 1000 对于100%的测试点 1 ≤ M ≤ 200000
请注意程序实现细节对效率的影响.
【来源】
LPZ原创，并提供数据和标程
这道题就是一道单纯的线段树，其实比最大区间和还简单些。 我们建立一颗线段树，记录最小值，最大值和区间内的最小差值。 在合并是，只需要去右边的最小值减左边的最大值，在与分别的最小差值求个最小值就可以了。 查找也是一样。
详细代码如下：
#include<cstdlib> #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; typedef long long ll; const int maxn=400005; const ll inf=200000000005ll; struct qu { ll x,y; int id; }a[maxn]; struct shu { ll minv,maxv,cha; }; ll w[maxn*2],minv[maxn*2],maxv[maxn*2],cha[maxn*2]; int lc[maxn*2],rc[maxn*2],cnt=0; int n,tot=0,root; bool vis[maxn]={0}; char s[15]; void up(int now){ int l=lc[now],r=rc[now]; maxv[now]=max(maxv[l],maxv[r]); minv[now]=min(minv[l],minv[r]); cha[now]=min(cha[l],min(cha[r],minv[r]-maxv[l])); } void build(int &now,int l,int r) { now=++cnt; cha[now]=minv[now]=inf; maxv[now]=-inf; if(l==r) return; int m=(l+r)>>1; build(lc[now],l,m); build(rc[now],m+1,r); } void in(int now,int l,int r,int x) { if(l==r) {minv[now]=maxv[now]=w[x];return;} int m=(l+r)>>1; if(x<=m)in(lc[now],l,m,x); else in(rc[now],m+1,r,x); up(now); } void out(int now,int l,int r,int x) { if(l==r) {minv[now]=inf;maxv[now]=-inf;return;} int m=(l+r)>>1; if(x<=m)out(lc[now],l,m,x); else out(rc[now],m+1,r,x); up(now); } shu work(shu t1,shu t2) { shu ans; ans.minv=min(t1.minv,t2.minv); ans.maxv=max(t1.maxv,t2.maxv); ans.cha=min(t1.cha,min(t2.cha,t2.minv-t1.maxv)); return ans; } shu find(int now,int l,int r,int i,int j) { if(l>=i&&r<=j) return (shu){minv[now],maxv[now],cha[now]}; int m=(l+r)>>1; shu t1,t2; t1=t2=(shu){inf,-inf,inf}; if(i<=m) t1=find(lc[now],l,m,i,j); if(j>m) t2=find(rc[now],m+1,r,i,j); return work(t1,t2); } int read(){ int x=0; bool ok=0; char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-') ch=getchar(); while((ch>='0'&&ch<='9')||ch=='-') { if(ch=='-') ok=1; else x=x*10+ch-'0'; ch=getchar(); } return ok?-x:x; } void init(){ n=read(); int m=0,x; for(int i=1;i<=n;i++) { scanf("%s",s); w[++m]=x=read(); if(s[0]=='Q') a[i].id=1,a[i].x=x,w[++m]=a[i].y=read(); if(s[0]=='I') a[i].id=2,a[i].x=x; if(s[0]=='D') a[i].id=3,a[i].x=x; } sort(w+1,w+1+m); tot=1; for(int i=2;i<=m;i++) if(w[i]!=w[i-1]) w[++tot]=w[i]; for(int i=1;i<=n;i++) { a[i].x=lower_bound(w+1,w+1+tot,a[i].x)-w; if(a[i].id==1) a[i].y=lower_bound(w+1,w+1+tot,a[i].y)-w; } build(root,1,tot); } int main() { //freopen("delt.in","r",stdin); //freopen("delt.out","w",stdout); init(); shu ans; for(int i=1;i<=n;i++) { if(a[i].id==1) { ans=find(root,1,tot,a[i].x,a[i].y); if(ans.cha>=w[tot]-w[1]) printf("-1\n"); else printf("%d\n",ans.cha); } if(a[i].id==2) { if(!vis[a[i].x]) { in(root,1,tot,a[i].x); vis[a[i].x]=1; } } if(a[i].id==3) { if(vis[a[i].x]) { out(root,1,tot,a[i].x); vis[a[i].x]=0; } else printf("Failed\n"); } } return 0; }