不加平衡措施的BST

本来写的替罪羊,过了样例,交上去WA了。我想看看是不是替罪羊重构出了问题,于是把重构删掉了,感觉会T,结果A了。。。

跑的挺快的,用new开内存还只跑了5557ms

具体如何可持久化,就是在递归对一个节点进行修改时,先复制当前节点。这样的话,每次进行操作前,直接将当前根先指向历史根,然后跑函数,就不用每次把历史版本传参传下来了。

代码如下

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

const int MAXN = 5e5 + 5;
//const float Alpha = 0.7;
const int INF = 0x7fffffff;

int n;

struct Node{
    int val, cnt, siz, cov;
    Node* ch[2];
    
    Node() {}
    
    Node(int val) : val(val) {
        siz = cov = cnt = 1;
        ch[0] = ch[1] = NULL;
    }
};

Node *rt[MAXN];
//vector<Node*> vec;
stack<Node*> stk;

Node *newNode(int val = 0) {
    if (stk.empty()) return new Node(val);
    Node *p = stk.top(); stk.pop();
    *p = Node(val);
    return p;
}

Node *Copy(Node *now) {
    Node *p = newNode();
    *p = *now;
    return p;
}
/*
bool Bad(Node *now) {
    int ls = now->ch[0] ? now->ch[0]->cov : 0;
    int rs = now->ch[1] ? now->ch[1]->cov : 0;
    return (float)ls > (float)now->cov * Alpha || (float)rs > (float)now->cov * Alpha;
}
*/
void Update(Node *now) {
    now->siz = now->cnt + (now->ch[0] ? now->ch[0]->siz : 0) + (now->ch[1] ? now->ch[1]->siz : 0);
    now->cov = 1 + (now->ch[0] ? now->ch[0]->cov : 0) + (now->ch[1] ? now->ch[1]->cov : 0);
}
/*
void Dfs(Node *now) {
    if (!now) return;
    now = Copy(now);
    Dfs(now->ch[0]);
    if (now->cnt) vec.push_back(now);
    else stk.push(now);
    Dfs(now->ch[1]);
    now->ch[0] = now->ch[1] = NULL;
    Update(now);
}

void Rebuild(Node *&now, int l, int r) {
    if (l > r) return;
    int mid = l + r >> 1;
    now = vec[mid];
    Rebuild(now->ch[0], l, mid - 1);
    Rebuild(now->ch[1], mid + 1, r);
}
*/
void Insert(Node *&now, int k) {
    if (!now) {
        now = newNode(k);
        return;
    } 
    now = Copy(now);
    if (k < now->val) Insert(now->ch[0], k);
    else if (k == now->val) now->cnt++;
    else Insert(now->ch[1], k);
    Update(now);
    /*if (Bad(now)) {
        vec.clear();
        Dfs(now);
        int len = vec.size();
        Rebuild(now, 0, len - 1);
    }*/
}

void Remove(Node *&now, int k) {
    if (!now) return;
    now = Copy(now);
    if (k < now->val) {
        Remove(now->ch[0], k);
    } else if (k == now->val) {
        if (now->cnt > 0) now->cnt--;
    } else {
        Remove(now->ch[1], k);
    }
    Update(now);
}

int Rank(Node *now, int k) {
    if (!now) return 1;
    int ls = now->ch[0] ? now->ch[0]->siz : 0;
    if (k < now->val) return Rank(now->ch[0], k);
    else if (k == now->val) return ls + 1;
    else return Rank(now->ch[1], k) + ls + now->cnt; 
}

int Kth(Node *now, int k) {
    if (!now) return 0;
    int ls = now->ch[0] ? now->ch[0]->siz : 0;
    if (k <= ls) return Kth(now->ch[0], k);
    else if (k <= ls + now->cnt) return now->val;
    else return Kth(now->ch[1], k - ls - now->cnt);
}

int GetPre(Node *now, int k) {
    if (!now) return -INF;
    if (now->val >= k) return GetPre(now->ch[0], k);
    int ret = GetPre(now->ch[1], k);
    return ret == -INF ? (now->cnt ? now->val : GetPre(now->ch[0], k)) : ret;
}

int GetSuc(Node *now, int k) {
    if (!now) return INF;
    if (now->val <= k) return GetSuc(now->ch[1], k);
    int ret = GetSuc(now->ch[0], k);
    return ret == INF ? (now->cnt ? now->val : GetSuc(now->ch[1], k)) : ret;
}

int main() {
    cin >> n;
    int op, ver, k, res;
    for (int i = 1; i <= n; i++) {
        cin >> ver >> op >> k;
        rt[i] = rt[ver];
        if (op == 1) {
            Insert(rt[i], k);
        } else if (op == 2) {
            Remove(rt[i], k);
        } else if (op == 3) {
            res = Rank(rt[i], k);
            cout << res << endl;
        } else if (op == 4) {
            res = Kth(rt[i], k);
            cout << res << endl;
        } else if (op == 5) {
            res = GetPre(rt[i], k);
            cout << res << endl;
        } else {
            res = GetSuc(rt[i], k);
            cout << res << endl;
        }
    }
    return 0;
}

希望本题可以出毒瘤数据卡掉本篇题解