对于非毒瘤数据,替罪羊树是所有平衡树中跑的最快的

这道题思路就是开栈记录每次毁掉的房子,开数组记录每一个房子是否被毁,每次查询前驱和后继即可。

提供指针版替罪羊树的代码

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

using namespace std;

const int INF = 0x7f7f7f7f;
const int MAXN = 5e4 + 5;
const float Alpha = 0.7;

int n, m;
bool vis[MAXN];
stack<int> stk;
char op[5];

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

Node *rt;
vector<Node*> vec;
stack<Node*> tsh;

Node *newNode(int val) {
    if (tsh.empty()) return new Node(val);
    Node *ret = tsh.top(); tsh.pop();
    *ret = Node(val);
    return ret;
}

void Update(Node *now) {
    now->siz = now->exist + (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);
}

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 / now->cov > Alpha || (float)rs / now->cov > Alpha;
}

void Dfs(Node *now) {
    if (!now) return;
    Node *tmp = now;
    Dfs(now->ch[0]);
    if (now->exist) vec.push_back(now);
    else tsh.push(now);
    Dfs(now->ch[1]);
    tmp->ch[0] = tmp->ch[1] = NULL;
}

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);
    Update(now);
}

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

void Remove(Node *now, int k) {
    if (!now) return;
    if (now->val == k) now->exist = false;
    else if (k < now->val) Remove(now->ch[0], k);
    else if (k > now->val) Remove(now->ch[1], k);
    Update(now);
    if (!Bad(now)) return;
    vec.clear();
    Dfs(now);
    int len = vec.size();
    Rebuild(now, 0, len - 1);
}

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->exist ? 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->exist ? now->val : GetSuc(now->ch[1], k)) : ret;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    while (m--) {
        cin >> op;
        if (op[0] == 'D') {
            int x;
            cin >> x;
            Insert(rt, x);
            stk.push(x);
            vis[x] = true;
        } else if (op[0] == 'R') {
            int x = stk.top(); stk.pop();
            Remove(rt, x);
            vis[x] = false;
        } else if (op[0] == 'Q') {
            int x;
            cin >> x;
            if (vis[x]) {
                cout << '0' << endl;
                continue;
            }
            int l = GetPre(rt, x), r = GetSuc(rt, x);
            cerr << "L:" << l << ' ' << "R:" << r << endl;
            cout << (r == INF ? n + 1 : r) - (l == -INF ? 0 : l) - 1 << endl;
        }
    }
    return 0;
}