您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
这题用替罪羊树过的。
替罪羊树， 其实就是一种很暴力的方法。 如果一个节点的左子树节点个数大于它节点个数*alpha或者右子树节点个数大于节点个数*alpha。 那么就将这个节点及它的子树重构。
重构非常暴力， 就是把它变成一个序列， 然后不停的找中点。 相当于将之前的不平衡的二叉树变成了一个完全二叉树。
在删除时， 并不是直接删除， 而是将这个节点打个标记。
代码中， sz是有效节点的个数， 而cover是总结点的个数。 在删除的时候， 如果根节点的sz < alpha*cover。 那么就将整棵树重构。
#include <bits/stdc++.h> using namespace std;
#define MAXN 100010
const double alpha = 0.75;
struct node
{
int sz, cover, val;
bool exist;
node* ch[];
node()
{
ch[] = ch[] = NULL;
exist = false;
sz = cover = ;
}
node(int val):val(val)
{
sz = cover = ;
exist = true;
ch[] = ch[] = NULL;
}
void pushUp(node* tmp)
{
sz += tmp->sz;
cover += tmp->cover;
}
bool isBad()
{
int tmpL = ch[]?ch[]->cover:;
int tmpR = ch[]?ch[]->cover:;
if(tmpL > cover * alpha + ||
tmpR > cover * alpha + )
return true;
return false;
}
};
node* root = NULL;
void add(node*& p, int val, node** flag)
{
if(p == NULL) {
p = new node(val);
return ;
}
p->sz++;
p->cover++;
add(p->ch[val >= p->val], val, flag);
if(p->isBad()) {
flag = &p;
}
}
void Erase(node* p, int k)
{
int x = p->ch[]?p->ch[]->sz:;
int tmp = x + (int)(p->exist);
p->sz--;
if(p->exist && tmp == k) {
p->exist = false;
return ;
}
if(k <= tmp) {
Erase(p->ch[], k);
} else {
Erase(p->ch[], k - tmp);
}
}
void traval(node*& p, vector<node*>& v)
{
if(p == NULL)
return ;
traval(p->ch[], v);
if(p->exist) {
v.push_back(p);
}
traval(p->ch[], v);
}
void divide(node*& p, vector<node*>& v, int l, int r)
{
if(l > r)
return ;
if(p == NULL)
p = new node();
int mid = l + r >> ;
p = v[mid];
divide(p->ch[], v, l, mid - );
divide(p->ch[], v, mid + , r);
if(p->ch[])
p->pushUp(p->ch[]);
if(p->ch[])
p->pushUp(p->ch[]);
if(p->exist)
p->sz++;
p->cover++;
}
void rebuild(node*& p)
{
vector <node*> v;
traval(p, v);
divide(p, v, , v.size()-);
}
int Rank(node*& p, int x)
{
if(p == NULL)
return ;
int ret = ;
if(p->val >= x) {
ret = Rank(p->ch[], x);
} else {
int tmp = (p->ch[])?p->ch[]->sz:;
ret = tmp + (int)p->exist;
ret += Rank(p->ch[], x);
}
return ret;
}
int Kth(node*& p, int k)
{
if(p == NULL)
return ;
int tmp = (p->ch[])?p->ch[]->sz:;
if(p->exist && tmp + == k)
return p->val;
if(tmp >= k) {
return Kth(p->ch[], k);
} else {
return Kth(p->ch[], k - tmp - p->exist);
}
}
void Insert(int val)
{
node** flag = NULL;
add(root, val, flag);
if(flag != NULL) {
rebuild(*flag);
}
}
void Erase(int k)
{
Erase(root, k);
if((double)root->sz < (double)(alpha*root->cover))
rebuild(root);
}
int main()
{
int n, sign, x;
cin>>n;
while(n--) {
scanf("%d%d", &sign, &x);
switch(sign) {
case : Insert(x);break;
case : Erase(root, Rank(root, x));break;
case : printf("%d\n", Rank(root, x));break;
case : printf("%d\n", Kth(root, x));break;
case : printf("%d\n", Kth(root, Rank(root, x) - ));break;
case : printf("%d\n", Kth(root, Rank(root, x + )));break;
}
}
return ;
}