练习选讲（2023）

Jasper08 / 2023-06-10 / 原文

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;
}