mxqz替罪羊树 20pts

https://www.luogu.com.cn/record/97880725

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
struct ScapegoatTree {
    const double alpha = 0.6666;
    struct node {
        int val, ls, rs, cnt, tot, siz, tsiz, sum;
    } tree[N];
    int cnt, tot, rt, cur[N];
    inline bool isBad(int u) {
        return tree[u].cnt && (alpha * tree[u].tot <= double(max(tree[tree[u].ls].tot, tree[tree[u].rs].tot)) || double(tree[u].tsiz) < alpha * tree[u].tot);
    }
    void push_up(int u) {
        tree[u].tot = tree[tree[u].ls].tot + tree[tree[u].rs].tot + 1;
        tree[u].siz = tree[tree[u].ls].siz + tree[tree[u].rs].siz + tree[u].cnt;
        tree[u].tsiz = tree[tree[u].ls].tsiz + tree[tree[u].rs].tsiz + bool(tree[u].cnt);
    }
    void dfs(int u) {
        if (!u) return;
        dfs(tree[u].ls);
        if (tree[u].cnt) cur[tot ++] = u;
        dfs(tree[u].rs);
    }
    int build(int l, int r) {
        int mid = (l + r) >> 1;
        if (l >= r) return 0;
        tree[cur[mid]].ls = build(l, mid);
        tree[cur[mid]].rs = build(mid + 1, r);
        push_up(cur[mid]);
        return cur[mid];
    }
    inline void rebuild(int& u) {
        tot = 0, dfs(u);
        if (u == rt) rt = u = build(0, tot);
        else u = build(0, tot);
    }
    int insert(int u, int val) {
        if (!u) {
            u = ++ cnt;
            if (!rt) rt = u;
            tree[u].val = val;
            tree[u].siz = tree[u].cnt = 1;
        } else {
            if (tree[u].val == val) tree[u].cnt ++;
            if (val < tree[u].val) tree[u].ls = insert(tree[u].ls, val);
            if (val > tree[u].val) tree[u].rs = insert(tree[u].rs, val);
            push_up(u);
            if (isBad(u)) rebuild(u);
        }
        return u;
    }
    void del(int u, int val) {
        if (!u) return;
        if (tree[u].val == val) tree[u].cnt --;
        if (val < tree[u].val) del(tree[u].ls, val);
        if (val > tree[u].val) del(tree[u].rs, val);
        push_up(u);
    }
    int query(int u, int val) {
        if (!u) return 0;
        if (tree[u].val == val) return tree[tree[u].ls].siz;
        if (val < tree[u].val) return query(tree[u].ls, val);
        return query(tree[u].rs, val) + tree[tree[u].ls].siz + tree[u].cnt;
    }
    int queryval(int u, int val) {
        if (!u) return 0;
        if (tree[u].val == val) return tree[tree[u].ls].sum;
        if (val < tree[u].val) return query(tree[u].ls, val);
        return query(tree[u].rs, val) + tree[tree[u].ls].siz + tree[u].val;
    }
    int Kth(int u, int k) {
        if (!u) return INT_MAX;
        if (tree[tree[u].ls].siz >= k) return Kth(tree[u].ls, k);
        if (tree[tree[u].ls].siz + tree[u].cnt >= k) return tree[u].val;
        return Kth(tree[u].rs, k - tree[tree[u].ls].siz - tree[u].cnt);
    }
    void print(int u) {
        if (!u) return;
        print(tree[u].ls);
        print(tree[u].rs);
        cout << tree[u].val << ' ' << tree[u].cnt << '\n';
    }
} T;
int n, q, c, s, a[N];
char opt;
int main() {
    cin >> n >> q;
    for (int i = 1; i <= q; i ++) {
        cin >> opt >> c >> s;
        if (opt == 'U') {
            if (a[c]) T.del(T.rt, a[c]);
            if (s) T.insert(T.rt, s);
            a[c] = s;
        }
        if (opt == 'Z') {
            int cnt = T.tree[T.rt].siz - T.query(T.rt, s), res = T.queryval(T.rt, s);
            puts(res >= (c - cnt) * s ? "TAK" : "NIE");
        }
    }
    return 0;
}