```cpp
#include <bits/stdc++.h>
using namespace std;
// const int kMaxN = 1600000 + 10;
const int kMaxN = 200000 + 10;
const float kAlpha = 0.75;
struct ScapegoatTree {
struct Node {
int val;
int l,r;
int siz;
int cnt;
bool exist;
};
Node tree[kMaxN];
int root, top;
void Print(int node) {
if (node == root) printf("Print: ");
if (!node) {
if (node == root) printf("\n");
return;
}
Print(tree[node].l);
if (tree[node].exist) {
printf("%d[%d] ", node, tree[node].val);
} else {
printf("~~%d[%d]~~ ", node, tree[node].val);
}
Print(tree[node].r);
if (node == root) printf("\n");
}
void PrintTree(int node, int level) {
if (!node) return;
PrintTree(tree[node].l, level + 1);
for (int i = 1; i <= level; i++) printf(" ");
if (tree[node].exist) {
printf("%d[%d]\n", node, tree[node].val);
} else {
printf("~~%d[%d]~~\n", node, tree[node].val);
}
PrintTree(tree[node].r, level + 1);
}
bool IsBad(int node) {
return tree[node].cnt * kAlpha <=
max(tree[tree[node].l].cnt, tree[tree[node].r].cnt);
}
int NewNode(int k) {
top++;
tree[top].val = k;
tree[top].siz = 1;
tree[top].cnt = 1;
tree[top].exist = true;
return top;
}
void PushUp(int node) {
tree[node].siz = tree[tree[node].l].siz + tree[tree[node].r].siz
+ tree[node].exist;
tree[node].cnt = tree[tree[node].l].cnt + tree[tree[node].r].cnt + 1;
}
vector<int> vec;
int* res;
void Collect(int node) {
if (!node) return;
Collect(tree[node].l);
if (tree[node].exist) vec.push_back(node);
Collect(tree[node].r);
}
int Build(int begin, int end) { // [begin, end)
if (begin == end) {
return 0;
} else {
int mid = (begin + end) >> 1;
tree[vec[mid]].l = Build(begin, mid);
tree[vec[mid]].r = Build(mid + 1, end);
PushUp(vec[mid]);
return vec[mid];
}
}
void Maintain() {
if (res) {
vec.clear();
Collect(*res);
*res = Build(0, vec.size());
}
}
void Insert(int& node, int val) {
if (node == root) res = nullptr; // 这里的if可有可无
if (!node) {
node = NewNode(val);
} else if (val <= tree[node].val) {
Insert(tree[node].l, val);
} else {
Insert(tree[node].r, val);
}
PushUp(node);
if (IsBad(node)) res = &node;
if (node == root) Maintain();
}
void Delete(int node, int val) {
if (!node) {
return;
} else if (val == tree[node].val && tree[node].exist) {
tree[node].exist = false;
} else if (val <= tree[node].val) {
Delete(tree[node].l, val);
} else {
Delete(tree[node].r, val);
}
PushUp(node);
}
int GetRank(int node, int val) {
if (!node) {
return 1;
} else if (val <= tree[node].val) {
return GetRank(tree[node].l, val);
} else {
return tree[tree[node].l].siz + tree[node].exist
+ GetRank(tree[node].r, val);
}
}
int GetKth(int node, int k) {
if (k <= tree[tree[node].l].siz) {
return GetKth(tree[node].l, k);
} else {
int mid = tree[tree[node].l].siz + tree[node].exist;
if (k == mid) {
return tree[node].val;
} else {
return GetKth(tree[node].r, k - mid);
}
}
}
int GetPre(int node, int val) {
return GetKth(node, GetRank(node, val) - 1);
}
int GetSuf(int node, int val) {
return GetKth(node, GetRank(node, val + 1));
}
};
ScapegoatTree sgt;
int n;
int main() {
freopen("testdata.in", "r", stdin);
freopen("testdata1.out", "w", stdout);
scanf("%d", &n);
while (n--) {
// sgt.Print(sgt.root);
// sgt.PrintTree(sgt.root, 0);
int opt, x;
scanf("%d %d", &opt, &x);
if (opt == 1) {
sgt.Insert(sgt.root, x);
} else if (opt == 2) {
sgt.Delete(sgt.root, x);
} else if (opt == 3) {
printf("%d\n", sgt.GetRank(sgt.root, x));
// printf(">>>>>> %d\n", sgt.GetRank(sgt.root, x));
} else if (opt == 4) {
printf("%d\n", sgt.GetKth(sgt.root, x));
// printf(">>>>>> %d\n", sgt.GetKth(sgt.root, x));
} else if (opt == 5) {
printf("%d\n", sgt.GetPre(sgt.root, x));
} else if (opt == 6) {
printf("%d\n", sgt.GetSuf(sgt.root, x));
} else {
printf("Illegal command.\n");
}
}
return 0;
}
```
by longlongzhu123 @ 2019-02-23 16:14:00