Lxzyzby Lxzyzby

Luogu P1486 [NOI2004]郁闷的出纳员

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

题目链接

我们只查询第 $k$ 大的权值是多少,所以我们维护一个权值的相对先后关系就可以了

把之前插入的所有数加 $x$ 相当于把后面插入的数减 $x$ ,这样相对位置就很好的维护出来了。

在扣除工资 $k$ 的时候,把整颗平衡树每个权值 $val[rt]+Sum<min$ 的点及其左子树全部放到 $x$ 树里,其他放到 $y$ 树里,这样分裂完两棵树后,把根设为 $y$ 即可,相当于把 $x$ 树删除

离开公司的人数就是 分裂时 $x$ 树的人数和

#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 = 1e6;
#define int long long
mt19937 Rand(time(0));
struct FHQ_Treap {
    int val[MAXN], siz[MAXN], rnd[MAXN], ls[MAXN], rs[MAXN];
    int cnt, root, lef;
    int newNode(int x) {
        int cur = ++cnt;
        val[cur] = x; siz[cur] = 1; rnd[cur] = Rand();
        ls[cur] = rs[cur] = 0; return cur;
    }
    void PushUp(int rt) {
        siz[rt] = 1; 
        if(ls[rt]) siz[rt] += siz[ls[rt]];
        if(rs[rt]) siz[rt] += siz[rs[rt]];
    }
    void split(int rt, int C, int &x, int &y) {
        if(!rt) return x = y = 0, void();
        if(val[rt] <= C) x = rt, split(rs[rt], C, rs[rt], y);
        else y = rt, split(ls[rt], C, x, ls[rt]);
        PushUp(rt);
    }
    void split_delete(int rt, int C, int lim, int &x, int &y) {
        if(!rt) return x = y = 0, void();
        if(val[rt] + C < lim) x = rt, split_delete(rs[rt], C, lim, rs[rt], y), lef += siz[ls[rt]] + 1;
        else y = rt, split_delete(ls[rt], C, lim, x, ls[rt]);
        PushUp(rt);
    }
    int merge(int x, int y) {
        if(!x || !y) return x + y;
        if(rnd[x] < rnd[y]) return rs[x] = merge(rs[x], y), PushUp(x), x;
        else return ls[y] = merge(x, ls[y]), PushUp(y), y;
    }
    void insert(int C) {
        int x, y;
        split(root, C, x, y);
        root = merge(merge(x, newNode(C)), y);
    } 
    void Delete(int C, int lim) {
        int x, y;
        split_delete(root, C, lim, x, y);
        root = y; 
    }
    int kth(int k) {
        int rt = root;
        while(true) {
            if(k <= siz[ls[rt]]) rt = ls[rt];
            else if(siz[ls[rt]] + 1 == k) return val[rt];
            else k -= siz[ls[rt]] + 1, rt = rs[rt];
        }
    }

}t;
int n, m, sum;
void SubtaskI() {
    int x; cin >> x;
    if(x < m) return ;
    t.insert(x - sum);
}
void SubtaskA() {
    int x; cin >> x;
    sum += x;
}
void SubtaskS() {
    int x; cin >> x;
    sum -= x;
    t.Delete(sum, m);

}
void SubtaskF() {
    int k; cin >> k;
    if(k > t.siz[t.root]) return cout << -1 << endl, void();
    k = t.siz[t.root] - k + 1;
    cout << t.kth(k) + sum<< endl;
}
int32_t main() {
    #ifdef ONLINE_JUDGE
    #else
        freopen("input","r",stdin);
    #endif
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        char opt[10]; cin >> opt;
        if(opt[0] == 'I') SubtaskI();    
        if(opt[0] == 'A') SubtaskA();
        if(opt[0] == 'S') SubtaskS();
        if(opt[0] == 'F') SubtaskF();
    }
    cout << t.lef;
    return 0;
}

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

FHQ Treap
发表新评论
仅有 1 条评论
  1. YuhangQ
    YuhangQ 10Chrome 86
    回复

    TQL

博客已萌萌哒运行
© 2020 由 Typecho 强力驱动.Theme by YoDu
PREVIOUS NEXT
雷姆
拉姆