6 月
6.9：
P1486 [NOI2004] 郁闷的出纳员：平衡树（蓝）
题解：
用一个变量 \(delta\) 记录员工们的工资变化量。
对于插入操作 I k，向平衡树中插入一个数 \(k-delta\)（其他人都增加了 \(delta\)，但他没有增加，相当于其他人不增加，他减小 \(delta\)）。
对于全局加法操作 A k，直接将 \(delta\) 增加 \(k\) 即可。
对于全局减法操作 S k，将 \(delta\) 减少 \(k\)，同时删除平衡树中小于 \(min-delta\) 的数（与插入操作思想类似）。
对于查询排名操作 F k，在平衡树上二分查找即可。若遍历到 \(0\) 号节点则返回 \(-1\)。
用 fhq-treap 实现，时间复杂度 \(O(n\log n)\)。
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 3e5+10;
int n, minl, ans, delta, idx, root; // delta 表示所有员工的工资变化量
struct Node {
int l, r;
int val, key; // BST, 堆
int size;
} tree[N];
void pushup(int u) {
tree[u].size = tree[tree[u].l].size + tree[tree[u].r].size + 1;
}
int newNode(int v) {
++ idx;
tree[idx].l = tree[idx].r = 0;
tree[idx].val = v, tree[idx].key = rand();
tree[idx].size = 1;
return idx;
}
void split(int p, int v, int &x, int &y) { // 按 v 分裂子树, 左子树小于等于x, 右子树大于x
if (!p) {x = y = 0; return ;}
if (tree[p].val <= v) {
x = p;
split(tree[p].r, v, tree[p].r, y);
} else {
y = p;
split(tree[p].l, v, x, tree[p].l);
}
pushup(p);
}
int merge(int x, int y) { // 合并子树, x中的值均小于y中的值
if (!x || !y) return x + y;
if (tree[x].key <= tree[y].key) {
tree[x].r = merge(tree[x].r, y);
pushup(x); return x;
} else {
tree[y].l = merge(x, tree[y].l);
pushup(y); return y;
}
}
void insert(int v) { // 插入 v
int x, y, z;
split(root, v, x, z);
y = newNode(v);
root = merge(merge(x, y), z);
}
void del(int v) { // 删除小于v的数
int x, y;
split(root, v-1, x, y);
ans += tree[x].size;
root = y;
}
int get_num(int p, int k) { // 在以p为根的子树内查询第 k 大数
if (!p) return -1;
if (tree[tree[p].r].size >= k) return get_num(tree[p].r, k);
if (tree[tree[p].r].size+1 == k) return tree[p].val;
return get_num(tree[p].l, k-tree[tree[p].r].size-1);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> minl;
char op; int k;
while (n -- ) {
cin >> op >> k;
if (op == 'I') {
if (k < minl) continue;
insert(k-delta);
} else if (op == 'A') {
delta += k;
} else if (op == 'S') {
delta -= k;
del(minl-delta);
} else {
int t = get_num(root, k);
cout << ((t == -1) ? t : t+delta) << '\n';
}
}
cout << ans << '\n';
return 0;
}