代码在这：
```#include<cstdio>
using namespace std;
struct node{
node*son[2];
node*fa;
int sum;
int num;
int data;
int weight;
void add(int);
void rem(int);
int rank(int);
node* ranker(int);
node(int,int);
}*root;
node::node(int x,int o){
num=sum=0;
weight=x;
data=o;
son[0]=son[1]=nullptr;
}
void node::add(int x){
++sum;
if(x==data)++num;
else if(son[x>=data+(weight>>1)])return son[x>=data+(weight>>1)]->add(x);
else{
son[x>=data+(weight>>1)]=new node(weight>>1,data+(x>=data+(weight>>1))*(weight>>1));
return son[x>=data+(weight>>1)]->add(x);
}
}
void node::rem(int x){
--sum;
if(x==data)--num;
else return son[x>=data+(weight>>1)]->rem(x);
}
int node::rank(int x){
if(x==data)return 1;
else return son[x>=data+(weight>>1)]->rank(x)+(x>=data+(weight>>1))*(sum-son[x>=data+(weight>>1)]->sum);
}
node* node::ranker(int x){
if(son[0]&&x<=son[0]->sum){
return son[0]->ranker(x);
}
if(!son[0]&&x<=num||son[0]&&x<=num+son[0]->sum)return this;
else return son[1]->ranker(x-sum+son[1]->sum);
}
int fronter(int x){
root->add(x);
int ans=root->ranker(root->rank(x)-1)->data;
root->rem(x);
return ans;
}
int nexter(int x){
root->add(x);
int ans=root->ranker(root->ranker(root->rank(x))->num+root->rank(x))->data;
root->rem(x);
return ans;
}
int main(){
int n;
int opt;
int x;
root=new node(33554432,0);
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d%d",&opt,&x);
if(opt==1){
root->add(x+16777216);
continue;
}
if(opt==2){
root->rem(x+16777216);
continue;
}
if(opt==3){
printf("%d\n",root->rank(x+16777216));
continue;
}
if(opt==4){
printf("%d\n",root->ranker(x)->data-16777216);
continue;
}
if(opt==5){
printf("%d\n",fronter(x+16777216)-16777216);
continue;
}
if(opt==6){
printf("%d\n",nexter(x+16777216)-16777216);
continue;
}
}
return 0;
}
```
by Gumbo @ 2022-03-27 15:39:20
@[OI_Beater](/user/478861)
在 321 ~ 322 行通过修改 infile 和 outfile 来改输入文件和答案文件。
随机数据。
```cpp
//
// Created by Cat-shao on 2021/11/14.
//
//
// Created by Cat-shao on 2021/8/10.
//
// 原始WBT
#include <bits/stdc++.h>
using namespace std;
const int Delta = 3;
const int Gamma = 2;
const int MAX_N = 100000;
class WBT {
public:
class node {
public:
node *parent; // 父节点指针
node *child[2]; // child[0]为左子结点的指针，child[1]为右子结点的指针。
int value, count, size, cover; // 数据，结点个数，size为有效结点的数量（记录count），cover为总结点的数量（全视为1）
};
node memoryPool[MAX_N];
node *tail; // 内存池使用的最后一个结点的下一个（tail没有被占用）
node *delNodes[MAX_N]; // 被删除结点的指针，循环利用
int delTop; // delNodes栈顶，同样没有被占用
node * newNode(int _value) {
node *current;
if (delTop) {
current = delNodes[--delTop];
} else {
current = tail++;
}
current->value = _value;
current->parent = current->child[0] = current->child[1] = NULL;
current->size = current->cover = current->count = 1;
return current;
}
void deleteNode(node *current) {
if (current == NULL) {
return;
}
delNodes[delTop++] = current;
}
node *root;
WBT() {
root = NULL;
tail = memoryPool;
delTop = 0;
}
void maintain(node *current) {
if (current == NULL) { // 可能传入的是一个空指针
return;
}
current->size = current->count;
current->cover = 1;
for (int i = 0; i < 2; ++i) {
if (current->child[i]) {
current->size += current->child[i]->size; // 加上左右子树的size
current->cover += current->child[i]->cover; // 加上左右子树的cover
}
}
}
int getType(node *current) { // 获得结点是左结点还是右结点，0左1右
if (current == NULL || current->parent == NULL) { // 传入空指针；根结点没有父亲，特判一下
return 0; // 下标放-1会报错，放个0就好了
}
return current->parent->child[1] == current; // 父亲的右子结点 是不是 自己
}
void connect(node *parent, node *current, int type) { // 父结点指针，当前结点指针，类型（0左1右）
if (parent) { // parent 可能为NULL
parent->child[type] = current;
}
if (current) { // current 也可能为NULL
current->parent = parent;
}
}
void DEBUGER(char fileName[], node *rt) { // 使用了splay part 2中的软件来绘图，调试神器
FILE *fp = NULL;
fp = fopen(fileName, "w");
fprintf(fp, "digraph {\n");
deque<node*> q; // 前序遍历，使用队列实现
node *current;
q.push_back(rt);
while (!q.empty()) {
current = q.front();
q.pop_front();
if (current == NULL) {
continue;
}
fprintf(fp, "\tn%d[label = \"%d\"]\n", current, current->value);
for (int i = 0; i < 2; ++i) {
if (current->child[i]) {
fprintf(fp, "\tn%d -> n%d[style = blod, taillabel = \"%d\"]\n", current, current->child[i], current->count);
q.push_back(current->child[i]);
} else {
fprintf(fp, "\tnull%d%d[label = \"NULL\", style = dotted]\n", current, i);
fprintf(fp, "\tn%d -> null%d%d[style = dotted, taillabel = \"%d\"]\n", current, current, i, current->count);
}
}
}
fprintf(fp, "}");
fclose(fp);
}
void rotate(node *parent, int type) { // type: 0左旋，1右旋
if (parent == NULL) {
return;
}
node *current = parent->child[type ^ 1];
if (current == NULL) {
return;
}
node *grandParent = parent->parent;
int parentType = getType(parent);
connect(parent, current->child[type], type ^ 1); // 将三角形结点挂到parent下
connect(current, parent, type); // 儿子变爹，爹变儿子
if (parent == root) {
root = current;
}
connect(grandParent, current, parentType); // 爷爷承认新的子节点
maintain(parent);
maintain(current);
}
int getWeight(node *current) {
if (current == NULL) {
return 1;
} else {
return current->cover + 1;
}
}
bool isBalanced(node *a, node *b) {
return Delta * getWeight(a) >= getWeight(b);
}
bool isSingle(node *a, node *b) {
return getWeight(a) < Gamma * getWeight(b);
}
void balance(node *current) {
if (current == NULL) {
return;
}
while (current != NULL) {
maintain(current);
for (int type = 0; type < 2; ++type) {
if (!isBalanced(current->child[type], current->child[type ^ 1])) { // 左子树小左旋
if (!isSingle(current->child[type ^ 1]->child[type], current->child[type ^ 1]->child[type ^ 1])) { // 双旋
rotate(current->child[type ^ 1], type ^ 1);
}
rotate(current, type);
break;
}
}
current = current->parent;
}
}
void updateSize(node *current) {
while (current) {
maintain(current);
current = current->parent;
}
}
node* insert(int value) {
if (root == NULL) {
root = newNode(value);
return root;
}
node *current = root;
node *parent = current->parent;
int type; // 类型
while (current) { // 和查找一模一样
if (current->value < value) {
parent = current;
current = current->child[1];
type = 1;
} else if (current->value > value) {
parent = current;
current = current->child[0];
type = 0;
} else { // 已经有相同结点了，将其count++即可。
current->count ++;
updateSize(current);
return current;
}
}
current = newNode(value);
connect(parent, current, type);
balance(current);
return current;
}
node *minMax(node *current, int type) { // type == 0为min，type == 1为max
while (current->child[type]) {
current = current->child[type];
}
return current;
}
void transplant(node *u, node *v) { // 把v换到u的位置来，只跟父节点打通关系
if (u == root) {
root = v;
}
connect(u->parent, v, getType(u));
}
void remove(node *current) {
if (current == NULL) {
return;
}
if (current->count >= 2) {
current->count --;
updateSize(current); // 更新size
return;
}
node *del;
if (current->child[0] == NULL) {
transplant(current, current->child[1]);
del = current;
} else if (current->child[1] == NULL) {
transplant(current, current->child[0]);
del = current;
} else {
node *maximum = minMax(current->child[0], 1); // 把maximum真正移上来容易出问题，这里把maximum的值换到current里了，变相删除current
current->value = maximum->value;
current->count = maximum->count;
transplant(maximum, maximum->child[0]);
del = maximum;
}
balance(del->parent);
deleteNode(del);
}
node* find(int value) {
node *current = root; // 从根结点开始搜索
while (current) {
if (current->value < value) {
current = current->child[1]; // 小了，往大了走
} else if (current->value > value) {
current = current->child[0]; // 大了，往小了走
} else { // 不大也不小不就是找到了吗？
return current;
}
}
return NULL; // 找不到结点，退出。（找到得到结点的话会在while循环就退出）
}
int rankOfNode(int value) { // 即使查询的值不在树中，也能查。
// 这里传入的value为被查询排名的结点的value
node *current = root; // 从根结点开始搜索
int leftSize = 1; // 左面的结点个数。提前将自己的大小1加上，你就想最左侧结点左面啥也没有但是排名为1
while (current) {
if (current->value >= value) { // 玄学。即使找到了结点， 也还是会往左走到NULL结点后退出，走左子树不加，不影响结果。
current = current->child[0];
} else {
if (current->child[0]) {
leftSize += current->child[0]->size;
}
leftSize += current->count;
current = current->child[1];
}
}
return leftSize;
}
node* nodeOfRank(int rank) {
node *current = root; // 从根结点查找
int leftSize; // 临时变量，用于记录左子树大小（左子树可能没有），和上面的leftSize不一样
while (current) {
if (current->child[0]) {
leftSize = current->child[0]->size;
} else {
leftSize = 0;
}
if (rank > leftSize) {
rank -= leftSize + current->count;
if (rank <= 0) { // 减去了count，可能直接减出负数。如果减去左子树大小和当前结点大小之后为0或者负数，那么这个结点
return current;
}
current = current->child[1]; // 不是在左子树、当前结点，就是在右子树呗
} else {
current = current->child[0];
}
}
return NULL;
}
};
int randint(int l, int r) {
return rand() % (r - l + 1) + l;
}
int main()
{
srand(time(0));
ofstream infile, ansfile;
infile.open("test.in", ios::out);
ansfile.open("test.ans", ios::out);
int n, opt, x;
WBT tree;
n = 50;
int MAX_V = 10;
infile << n << endl;
for (int i = 1; i <= n; i++) {
if (tree.root == NULL) {
opt = 1;
x = randint(1, MAX_V);
} else {
opt = randint(1, 2);
if (opt == 2) {
opt = randint(2, 6);
}
if (opt == 4) {
x = randint(1, tree.root->size);
} else if (opt == 5) {
int temp = tree.minMax(tree.root, 0)->value + 1;
x = randint(temp, max(temp, MAX_V));
} else if (opt == 6) {
int temp = tree.minMax(tree.root, 1)->value - 1;
x = randint(min(temp, 0), temp);
} else if (opt == 2 || opt == 3) {
x = tree.nodeOfRank(randint(1, tree.root->size))->value;
} else {
x = randint(1, MAX_V);
}
}
infile << opt << " " << x << endl;
switch (opt) {
case 1: tree.insert(x); break;
case 2: tree.remove(tree.find(x)); break;
case 3: ansfile << tree.rankOfNode(x) << endl; break;
case 4: ansfile << tree.nodeOfRank(x)->value << endl; break;
case 5: ansfile << tree.nodeOfRank(tree.rankOfNode(x) - 1)->value << endl; break;
case 6: ansfile << tree.nodeOfRank(tree.rankOfNode(x + 1))->value << endl; break;
}
}
infile.close();
ansfile.close();
return 0;
}
```
by Cat_shao @ 2022-03-28 12:00:49
@[Cat_shao](/user/234011) 感谢
by Gumbo @ 2022-03-28 16:51:12