一道平衡树实现的名次树，用了treap实现。
1.rand（）产生的数可能比INF大，很可能改变树的结构。
2.删除时先递归，然后再删除自己，实现就变得简单多了。
3.因为很多情况树会是空的，所以设了一个root虚拟节点。设指针时一定要new一个出来。
就这样，其实水题一道。
#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int maxn = 100000 + 10;
const int INF = 1000000000 + 7; int n,minv,p = 0,ans = 0,sum; struct Node {
int v,r,s;
Node* ch[2]; int cmp(int x) const {
if(v == x) return -1;
return v < x ? 0 : 1;
} void maintain() {
s = 1;
if(ch[0] != NULL) s += ch[0]->s;
if(ch[1] != NULL) s += ch[1]->s;
} } a[maxn]; Node *root = new Node(); void rotate(Node* &o,int d) {
Node* k = o->ch[d^1];
o->ch[d^1] = k->ch[d];
k->ch[d] = o;
o->maintain();
k->maintain();
o = k;
} void insert(Node* &o,int x) {
if(o == NULL) {
o = &a[p++];
o->v = x;
o->ch[0] = o->ch[1] = NULL;
o->r = rand()%INF;
o->s = 1;
}
else {
int d = o->v > x ? 0:1;
insert(o->ch[d],x);
if(o->ch[d]->r > o->r) rotate(o,d^1);
o->maintain();
}
} void remove(Node* &o,int x) {
if(o == NULL) return;
if(o->v >= x) {
remove(o->ch[0],x);
o->maintain();
}
else {
remove(o->ch[0],x);
remove(o->ch[1],x);
if(o->ch[1] == NULL) {
o = NULL;
ans++;
}
else {
rotate(o,0);
remove(o->ch[0],x);
o->maintain();
}
}
} int find(Node* o,int k) {
if(o == root) {return find(o->ch[0],k);}
else {
if(o == NULL) return (-1);
int m;
if(o->ch[1] == NULL) m = 0;
else m = o->ch[1]->s;
if(k == m+1) return o->v;
else if(k < m+1) return find(o->ch[1],k);
else return find(o->ch[0],k-m-1);
}
} char s[10]; int main() {
scanf("%d%d",&n,&minv);
root->v = root->r = INF;
root->s = 1;
while(n--) {
int v;
scanf("%s%d",s,&v);
if(s[0] == 'I') if(v >= minv) {insert(root,v-sum);};
if(s[0] == 'A') sum += v;
if(s[0] == 'S') {
sum -= v;
remove(root,minv-sum);
}
if(s[0] == 'F') {
if(root->s-1 < v) printf("-1\n");
else printf("%d\n",find(root,v)+sum);
}
}
printf("%d\n",ans);
return 0;
}