「SCOI2011」「LOJ #2441」 棘手的操作

Description

有 (n) 个节点，标号从 (1) 到 (n)，这 (n) 个节点一开始相互不连通。第 (i) 个节点的初始权值为 (a_i)，接下来有如下 (m) 个操作：

• U x y: 加一条边，连接第 (x) 个节点和第 (y) 个节点
• A1 x v: 将第 (x) 个节点的权值增加 (v)
• A2 x v: 将第 (x) 个节点所在的连通块的所有节点的权值都增加 (v)
• A3 v: 将所有节点的权值都增加 (v)
• F1 x: 输出第 (x) 个节点当前的权值
• F2 x: 输出第 (x) 个节点所在的连通块中，权值最大的节点的权值
• F3: 输出所有节点中，权值最大的节点的权值

Hint

• (1le n, mle 3 imes 10^5)
• (|a_i|, |v| le 10^3)

Solution

考虑到有查询最大值的操作，于是考虑用 大根堆。每个连通块用一个堆维护。

然而发现存在单点加操作，实现时需要先将原来的值删掉再重新插入。这就意味着需要在堆中删除一个特定值的元素，而显然朴素的堆不支持这个操作。

换成平衡树（multiset）？但是常数太大了比较危险，这里介绍一种 可删堆：

所谓可删堆，即在一般堆的基础上拓展一种删除操作。
我们可以开两个堆（同时为大根堆）dat, del。
插入元素时，在 dat 中插入要插入的值。
删除元素时，在 del 中插入要删除的值。
取最大值时，先判断 dat 和 del 的堆顶是否相同，如果不同则一直令两者同时弹出堆顶，直到堆顶不同或 del 为空。最后取 dat 的堆顶即为所求。

---

其中还要求支持全局的修改查找操作，于是在用一个大根堆去维护 所有大根堆的堆顶元素。

由于这些堆顶同样是会变的，于是同样用可删堆。

---

当两个连通块之间连边，那么会合并为一个连通块，两个堆也应该合并。

但是普通的二叉堆的合并只能一个个弹出来重新塞入另一个中，直接怎么干总复杂度就是 (O(n^2log n)) 的。

于是我们又引入一种新的合并方法——启发式合并：

启发式合并的意思是，小的合并到大的上，即从小的当中一个个抽出来，一个个塞到大的中。
这样做的总复杂度为 (O(nlog^2 n))。下面给出简单的证明：
对于小的中的元素，每次合并后，其所在的集合一定会至少扩大两倍。
那么小集合中的元素至多经历 (O(log n)) 次合并。
堆的一次插入或删除是 (O(log n)) 一次的，于是总复杂度为 (O(nlog^2 n))。

---

如何支持局部加？根据上面的思路，即为令一个堆的所有元素同时加一个值。

打标记！ 在合并和取值注意标记的影响。

---

在合并时有三个坑点：

1. 合并 (a, b)，并不是直接在这两个上操作，而是在其所在集合上操作，这个可以用 并查集 实现。
2. 在合并元素时，两个堆的标记不能直接相加，而是应该在合并中的元素上 加上原标记，减去新标记。
3. 在合并元素时，还应在根据标记在原数组上改动。为了快速找到这个堆中所有元素的位置，我们不妨新开一个 vector 记录位置信息，在合并时仍然启发式合并。

Code

/*
 * Author : _Wallace_
 * Source : https://www.cnblogs.com/-Wallace-/
 * Problem : SCOI2011 LOJ #2441 棘手的操作
 */
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <vector>

using namespace std;
const int N = 3e5 + 5;

struct numSet {
	priority_queue<int> dat, del;
	int add;
	inline void inc(int v) { dat.push(v); }
	inline void pop(int v) { del.push(v); }
	inline int top() {
		while (!del.empty() && dat.top() == del.top()) dat.pop(), del.pop();
		return dat.top() + add;
	}
	inline void destroy() {
		while (!dat.empty()) dat.pop();
		while (!del.empty()) del.pop();
	}
} num[N], all;
vector<int> pos[N];
int n, m;
int ary[N], fa[N];

int find(int x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y) {
	x = find(x), y = find(y);
	if (x == y) return;
	if (pos[x].size() < pos[y].size()) swap(x, y);
	
	all.pop(num[x].top());
	all.pop(num[y].top());
	
	for (auto i : pos[y]) {
		fa[i] = x;
		ary[i] += num[y].add - num[x].add;
		num[x].inc(ary[i]);
		pos[x].push_back(i);
	}
	pos[y].clear();
	
	all.inc(num[x].top());
	num[y].destroy();
}

signed main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (register int i = 1; i <= n; i++) {
		cin >> ary[i];
		num[i].inc(ary[i]);
		all.inc(ary[i]);
		pos[i].push_back(i);
		fa[i] = i;
	}
	
	cin >> m;
	while (m--)	 {
		string opt;
		int a, b;
		cin >> opt;
		
		if (opt == "U") {
			cin >> a >> b;
			merge(a, b);
		} else if (opt == "A1") {
			cin >> a >> b;
			int tmp = ary[a];
			ary[a] += b;
			a = find(a);
			all.pop(num[a].top());
			num[a].pop(tmp);
			num[a].inc(tmp + b);
			all.inc(num[a].top());
		} else if (opt == "A2") {
			cin >> a >> b;
			a = find(a);
			all.pop(num[a].top());
			num[a].add += b;
			all.inc(num[a].top());
		} else if (opt == "A3") {
			cin >> b;
			all.add += b;
		} else if (opt == "F1") {
			cin >> a;
			int tmp = ary[a];
			a = find(a);
			tmp += num[a].add;
			tmp += all.add;
			cout << tmp << endl;
		} else if (opt == "F2") {
			cin >> a, a = find(a);
			cout << num[a].top() + all.add << endl;
		} else {
			cout << all.top() << endl;
		}
	}
}