总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制: 262144kB
描述
给一个长为N的数列，有M次操作，每次操作是以下三种之一：

（1）插入一个数，若已存在则忽略

（2）删除一个数，若不存在则忽略

（3）求数列中任意两数之差绝对值的最小值

输入
第一行两个正整数N和M。
第二行N的整数表示这个数列。注意若有重复的数，则视作一个。
接下来M行，每行开头是一个字符，若该字符为’I’，则表示一个插入操作，接下来一个整数x，表示插入一个数x；若该字符为’D’，则表示一个删除操作，接下来一个整数x，表示删除一个数x；若该字符为’Q’，则表示一个询问操作，求数列中任意两数之差绝对值的最小值，若不存在至少两个数，输出-1。
输出
对每一个询问操作单独输出一行，表示答案。
样例输入
5 3
1 9 3 7 5
Q
I 2
Q
样例输出
2
1
提示
1<=N<=10^5，1<=M<=10^5，输入保证合法，且所有整数可用带符号32位整型存储。

solution:平衡树+堆/平衡树

数组要开两倍，不然一个下午就没有了。

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1e5 + 7;inline int randa(){static int seed=914;return seed=int(seed*28741LL%2147483647);
}struct Teap{int ls, rs, rd, v;long long ans;
}tr1[N<<1];int root1, cnt1;struct Treap_ans{int ls, rs, rd, w;long long v;
}tr2[N<<1];int root2, cnt2;int ans;void lrot1(int &nd){int t=tr1[nd].rs;tr1[nd].rs=tr1[t].ls; tr1[t].ls=nd; nd=t;
}
void lrot2(int &nd){int t=tr2[nd].rs;tr2[nd].rs=tr2[t].ls; tr2[t].ls=nd; nd=t;
}
void rrot1(int &nd){int t=tr1[nd].ls;tr1[nd].ls=tr1[t].rs; tr1[t].rs=nd; nd=t;
}
void rrot2(int &nd){int t=tr2[nd].ls;tr2[nd].ls=tr2[t].rs; tr2[t].rs=nd; nd=t;
}void ins(int &nd, int x){if( nd==0 ){nd=++cnt2; tr2[nd].v=x; tr2[nd].rd=randa(); tr2[nd].w=1;return ;}if( tr2[nd].v==x ) { tr2[nd].w++; return ; }if( x<tr2[nd].v ) { ins(tr2[nd].ls,x); if( tr2[tr2[nd].ls].rd>tr2[nd].rd ) rrot2(nd); }else { ins(tr2[nd].rs,x); if( tr2[tr2[nd].rs].rd>tr2[nd].rd ) lrot2(nd); }
}
void del(int &nd, int x){if( nd==0 ) return ;if( tr2[nd].v==x ){if( tr2[nd].w>1 ) { tr2[nd].w--; return; }if( tr2[nd].ls*tr2[nd].rs==0 ) nd=tr2[nd].ls+tr2[nd].rs;else if( tr2[tr2[nd].ls].rd>tr2[tr2[nd].rs].rd ) { rrot2(nd); del(nd,x); }else { lrot2(nd); del(nd,x); }} else if( x<tr2[nd].v ) del(tr2[nd].ls,x);else del(tr2[nd].rs,x);
}int Q(int nd, int flg){if( nd==0 ) return ans*flg;ans=nd;return Q(tr2[nd].ls,1);
}int q_pre(int nd, int x, int flg){if( nd==0 ) return ans*flg;if( tr1[nd].v<x ){ans=nd; return q_pre(tr1[nd].rs,x,1);} else return q_pre(tr1[nd].ls,x,flg);
}
int q_sub(int nd, int x, int flg){if( nd==0 ) return ans*flg;if( tr1[nd].v>x ){ans=nd; return q_sub(tr1[nd].ls,x,1);} else return q_sub(tr1[nd].rs,x,flg);
}void insert(int &nd, int x){if( nd==0 ){nd=++cnt1; tr1[nd].v=x; tr1[nd].rd=randa();int pre=q_pre(root1,x,0);int sub=q_sub(root1,x,0);if(pre!=0) { tr1[nd].ans=x-tr1[pre].v; ins(root2,tr1[nd].ans); }if(sub!=0) {
     del(root2,tr1[sub].ans); tr1[sub].ans=tr1[sub].v-x; ins(root2,tr1[sub].ans); }return;}if( tr1[nd].v==x ) return;if( x<tr1[nd].v ) { insert(tr1[nd].ls,x); if(tr1[tr1[nd].ls].rd>tr1[nd].rd ) rrot1(nd);}else { insert(tr1[nd].rs,x); if(tr1[tr1[nd].rs].rd>tr1[nd].rd ) lrot1(nd); }
}void remove(int &nd, int x){if( nd==0 ) return ;if( tr1[nd].v==x ){if( tr1[nd].ls*tr1[nd].rs==0 ) { del(root2,tr1[nd].ans);nd=tr1[nd].ls+tr1[nd].rs;int pre=q_pre(root1,x,0), sub=q_sub(root1,x,0);if(sub!=0) del(root2,tr1[sub].ans);if( sub!=0 && pre!=0 ) tr1[sub].ans=tr1[sub].v-tr1[pre].v;if( sub!=0 && pre!=0 ) ins(root2,tr1[sub].ans);}else if( tr1[tr1[nd].ls].rd>tr1[tr1[nd].rs].rd ) { rrot1(nd); remove(nd,x); }else { lrot1(nd); remove(nd,x); }} else if( x<tr1[nd].v ) remove(tr1[nd].ls,x);else remove(tr1[nd].rs,x);
}int main(){int n, m, x;scanf("%d%d", &n, &m );cnt1=cnt2=root1=root2=0;for ( int i=1; i<=n; i++ ) scanf("%d", &x ), insert(root1,x);int cnt=n;while( m-- ) {char ch[2];scanf("%s", ch);if( ch[0]=='I' ) cnt++,scanf("%d", &x ), insert(root1,x);if( ch[0]=='D' ) cnt--,scanf("%d", &x ), remove(root1,x);if( ch[0]=='Q' ){if( cnt<2 ) printf("-1\n");else  printf("%lld\n", tr2[Q(root2,0)].v ); }}
}