我已经翻来覆去看了好多遍了,依旧找不到问题,QAQ
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
const double ALPHA = 0.75;
const int N = 1e7+5;
struct Node
{
int L, R;
int value;
int size;
int cnt;
}tree[N];
int order[N], cnt;
int node_stack[N], top = 0;
//初始化节点栈
void init_stack()
{
top = 0;
for(int i = N-1; i >= 1; i--){
top++;
node_stack[top] = i;
}
}
//初始化节点
void init_node(int x)
{
tree[x].L = tree[x].R = 0;
tree[x].size = tree[x].cnt = 1;
}
//拍平树
void inorder(int x)
{
if(!x)return ;
inorder(tree[x].L);
if(tree[x].cnt)order[++cnt] = x;
else{
top++;
node_stack[top] = x;
}
inorder(tree[x].R);
}
void push_up(int x)
{
tree[x].size = tree[tree[x].L].size + tree[tree[x].R].size + tree[x].cnt;
}
//是否重构
bool notbalance(int p)
{
if(ALPHA*(tree[p].size) <= max(tree[tree[p].L].size, tree[tree[p].R].size))return true;
return false;
}
//建立
int build(int l, int r)
{
int mid = (l+r)/2, root = order[mid];
if(l == r){
init_node(root);
return root;
}
if(l < mid)tree[root].L = build(l, mid-1);
if(l == mid)tree[root].L = 0;
tree[root].R = build(mid+1, r);
push_up(root);
return root;
}
//插入
int insert(int p, int k)
{
if(!p){
int root = node_stack[top];
top--;
init_node(root);
tree[root].value = k;
return root;
}else{
if(tree[p].value == k)tree[p].cnt++;
else if(tree[p].value > k)tree[p].L = insert(tree[p].L, k);
else tree[p].R = insert(tree[p].R, k);
push_up(p);
if(notbalance(p)){
cnt = 0;
inorder(p);
if(cnt)p = build(1, cnt);
else p = 0;
}
return p;
}
}
//删除
void del_node(int p, int k)
{
if(!p)return ;
if(tree[p].value == k){
if(tree[p].cnt)tree[p].cnt--;
}else{
if(tree[p].value > k)del_node(tree[p].L, k);
else del_node(tree[p].R, k);
}
push_up(p);
}
//查询x的排名
int query_rank(int p, int x)
{
if(!p)return 0;
if(tree[p].value < x)return tree[tree[p].L].size + tree[p].cnt + query_rank(tree[p].R, x);
else return query_rank(tree[p].L, x);
}
//第x个
int rank_x(int p, int x)
{
if(!p)return 0;
if(tree[tree[p].L].size < x){
if(x-tree[tree[p].L].size <= tree[p].cnt)return tree[p].value;
else return rank_x(tree[p].R, x-tree[tree[p].L].size-tree[p].cnt);
}else return rank_x(tree[p].L, x);
}
int pre_node(int p, int x)
{
return rank_x(p, query_rank(p, x));
}
int next_node(int p, int x)
{
return rank_x(p, query_rank(p, x+1)+1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
init_stack();
int root = 0;
while(t--){
int op, x;
cin >> op >> x;
if(op == 1)root = insert(root, x);
else if(op == 2)del_node(root, x);
else if(op == 3)cout << query_rank(root, x)+1 << endl;
else if(op == 4)cout << rank_x(root, x) << endl;
else if(op == 5)cout << pre_node(root, x) << endl;
else if(op == 6)cout << next_node(root, x) << endl;
}
}