Lxzyzby Lxzyzby

Luogu P3850 [TJOI2007]书架

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

题目链接

模板题,简单的插入操作和查询操作

#include <bits/stdc++.h>
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 = 2e5+10;
namespace FHQ_Treap {
    int lc[MAXN], rc[MAXN], rnd[MAXN], siz[MAXN], fa[MAXN];
    int cnt, id[MAXN], val[MAXN], root;
    int newnodw(int x) {
        val[++cnt] = x; rnd[cnt] = rand(); siz[cnt] = 1; 
        fa[cnt] = lc[cnt] = rc[cnt] = 0; id[x] = cnt;
        return cnt;
    }
    void PushUp(int rt) {
        siz[rt] = 1;
        if(lc[rt]) siz[rt] += siz[lc[rt]], fa[lc[rt]] = rt;
        if(rc[rt]) siz[rt] += siz[rc[rt]], fa[rc[rt]] = rt;
    }
    void split(int rt, int C, int &x, int &y) {
        if(!rt) return x = y = 0, void();
        if(siz[lc[rt]] + 1 <= C) x = rt, split(rc[rt], C - siz[lc[rt]] - 1, 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 pos, int C) {
        int x, y;
        split(root, pos-1, x, y);
        root = merge(merge(x, newnodw(C)), y);
    }
    int kth(int k) {
        int ans, x, y, z;
        split(root, k, x, z);
        split(x, k-1, x, y);
        ans = val[y];
        return root = merge(merge(x, y), z), ans;
    }
}
using namespace FHQ_Treap;
int n, m, q, cur;
map<string, int> mp;
map<int, string> smp;
int main() {
    srand(time(0));
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        string str; cin >> str;
        mp[str] = ++cur; smp[cur] = str;
        root = merge(root, newnodw(cur));
    }
    cin >> m; 
    for(int i = 1; i <= m; i++) {
        string str; int pos; cin >> str >> pos; pos++;
        mp[str] = ++cur; smp[cur] = str;
        insert(pos, cur);
    }
    cin >> q;
    for(int i = 1; i <= q; i++) {
        int pos; cin >> pos;
        cout << smp[kth(pos+1)] << endl;
    }
    return 0;
}

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

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