Lxzyzby Lxzyzby

P3369 【模板】普通平衡树 FHQ Treap

in FHQ Treap read (43) 文章转载请注明来源!

新学的FHQ Treap记录一下

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef unsigned long long ull;
#define lsiz(x) int(x.size())
#define lch rt<<1
#define rch rt<<1|1
const ll Linf = 0x7f7f7f7f7f7f7f7f;
const int Inf = 0x3f3f3f3f;
const int MAXN = 1e5+10;
namespace FHQ_Treap {
    int lc[MAXN], rc[MAXN], rnd[MAXN], siz[MAXN], val[MAXN];
    int root, cnt;
    int newnode(int C) {
        val[++cnt] = C; lc[cnt] = rc[cnt] = 0; siz[cnt] = 1; rnd[cnt] = rand();
        return cnt;
    }
    void PushUp(int rt) {
        siz[rt] = siz[lc[rt]] + siz[rc[rt]] + 1;
    }
    void split(int rt, int C, int &x, int &y) {
        if(!rt) return x = y = 0, void();
        if(val[rt] <= C) x = rt, split(rc[rt], C, rc[rt], y);
        else y = rt, split(lc[rt], C, x, lc[rt]);
        PushUp(rt);
    }
    int merge(int x, int y) {
        if(!x || !y) return x + y;
        if(rnd[x] < rnd[y]) return rc[x] = merge(rc[x], y), PushUp(x), x;
        else return lc[y] = merge(x, lc[y]), PushUp(y), y; 
    }
    void insert(int C, int &rt = root) {
        int x, y;
        split(rt, C, x, y);
        x = merge(x, newnode(C)); 
        rt = merge(x, y);
    }
    void del_one(int C, int &rt = root) {
        int x, y, z;
        split(rt, C, x, z);
        split(x, C-1, x, y);
        y = merge(lc[y], rc[y]);
        rt = merge(merge(x, y), z);
    }
    int FindByVal(int C, int &rt = root) {
        int x, y, ans;
        split(rt, C-1, x, y);
        ans = siz[x] + 1;
        return rt = merge(x, y), ans;
    }
    int FindKth(int k, int &rt = root) {
        int x = rt;
        while(true) {
            if(k <= siz[lc[x]]) x = lc[x];
            else if(siz[lc[x]] + 1 == k) return val[x];
            else k -= siz[lc[x]] + 1, x = rc[x];
        }
    }
    int GetPre(int C, int &rt = root) {
        int x, y, ans;
        split(rt, C-1, x, y);
        ans = FindKth(siz[x], x);
        return rt = merge(x, y), ans;
    }
    int GetSuf(int C, int &rt = root) {
        int x, y, ans;
        split(rt, C, x, y);
        ans = FindKth(1, y);
        return rt = merge(x, y), ans;
    }
}
void Subtask1() {
    int x; cin >> x;
    FHQ_Treap::insert(x);
}
void Subtask2() {
    int x; cin >> x;
    FHQ_Treap::del_one(x);
}
void Subtask3() {
    int x; cin >> x;
    cout << FHQ_Treap::FindByVal(x) << endl;
}
void Subtask4() {
    int x; cin >> x;
    cout << FHQ_Treap::FindKth(x) << endl;
}
void Subtask5() {
    int x; cin >> x;
    cout << FHQ_Treap::GetPre(x) << endl;
}
void Subtask6() {
    int x; cin >> x;
    cout << FHQ_Treap::GetSuf(x) << endl;
}
int n;
int main() {
    #ifdef ONLINE_JUDGE
    #else
        freopen("input", "r", stdin);
    #endif
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int opt; cin >> opt;
        if(opt == 1) Subtask1();
        if(opt == 2) Subtask2(); 
        if(opt == 3) Subtask3();
        if(opt == 4) Subtask4();
        if(opt == 5) Subtask5();
        if(opt == 6) Subtask6();    
    }
    return 0;
}

本文基于《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
文章链接:https://zby.xyz/index.php/archives/81/ (转载时请注明本文出处及文章链接)

FHQ Treap
发表新评论
博客已萌萌哒运行
© 2020 由 Typecho 强力驱动.Theme by YoDu
PREVIOUS NEXT
雷姆
拉姆