本题第一篇替罪羊树题解

题解里以Splay和Treap为主。但是如果只做权值树,感觉替罪羊树码量最小,跑的还最快。毕竟暴力出奇迹

题目大意

给一组数据和两种操作,分别为插入一个数和查询第$k$大

解法

  • 使用替罪羊树维护,注意数据是从大到小排的
  • 对于给出的数据,降序排序后二分建树如果懒的话一个一个insert也问题不大,多个$log$无伤大雅
  • 对于两种操作,平衡树板子

代码

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

using namespace std;

const int MAXN = 1e5 + 5;
const double A = 0.8;

int a[MAXN];

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

    void Update() {
        siz = (ch[0] ? ch[0]->siz : 0) + (ch[1] ? ch[1]->siz : 0) + 1;
    }

    bool Bad() {
        int ls = ch[0] ? ch[0]->siz : 0, rs = ch[1] ? ch[1]->siz : 0;
        return (double)ls > (double)siz * A || (double)rs > (double)siz * A;
    }
};

Node *rt = NULL;

vector<Node*> vec;

void Build(Node *&now, int l, int r) {
    if (l > r) return;
    int mid = l + r >> 1;
    now = new Node(a[mid]);
    Build(now->ch[0], l, mid - 1);
    Build(now->ch[1], mid + 1, r);
    now->Update();
}

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

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

void Insert(Node *&now, int val) {
    if (now == NULL) {
        now = new Node(val);
        return;
    } else {
        Insert(val > now->val ? now->ch[0] : now->ch[1], val);
        now->Update();
        if (now->Bad()) {
            vec.clear();
            Dfs(now);
            int tot = vec.size();
            Rebuild(now, 0, tot - 1);
        }
    }
}
/*
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 + 1) return now->val;
    else return Kth(now->ch[1], k - ls - 1);
}
*/
int Kth(int rank) {
    if (!rt) return 1;
    Node *now = rt, *prev = NULL;
    while (now) {
        prev = now;
        int ls = now->ch[0] ? now->ch[0]->siz : 0;
        if (rank <= ls) now = now->ch[0];
        else if (rank <= ls + 1) break;
        else rank -= ls + 1, now = now->ch[1];
    }
    return prev->val;
}

int cmp(const void *a, const void *b) {
    return *(int*)b - *(int*)a;
}

int main() {
    ios :: sync_with_stdio(false); cin.tie(NULL);
    int m, q;
    cin >> m >> q;
    for (int i = 1; i <= m; i++) cin >> a[i];
    qsort(a + 1, m, sizeof(int), cmp);
    Build(rt, 1, m);
    for (int i = 1; i <= q; i++) {
        int op, x;
        cin >> op >> x;
        if (op == 1) 
            cout << Kth(x) << endl;
        else
            Insert(rt, x);
    }
    return 0;
}