求救,我已经找不出任何问题了,请求大佬帮助
查看原帖
求救,我已经找不出任何问题了,请求大佬帮助
905895
nick5185楼主2023/10/29 18:38

我已经翻来覆去看了好多遍了,依旧找不到问题,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;
    }
}
2023/10/29 18:38
加载中...