题目传送门(BZOJ)
>原文链接<

题解 :

​ 唔,看上去我们需要维护一个资瓷合并、实时查询更新最小值的数据结构。

—— 可并堆可以胜任这项任务。

​ 可并堆是一个堆式结构的二叉树,由于其左偏的性质,有类似启发式合并的复杂度 —— 单次操作 \Theta(\log n)

我们只要维护如下几个性质就好 :

  • val[p] \le val[ls[p]] \& val[p] \le val[rs[p]]
  • dis[ls] \ge dis[rs]
  • dis[p] = dis[rs]+1

满足后两个性质,意味着 dis[p] \le \log n 满足第一个性质,意味着它是一个堆。

现在我们考虑如何合并、合并的复杂度是什么

合并的复杂度是 \log siz[x] + \log siz[y]

合并两个堆,只要比较当前节点权值,而后将权值较大的与另一个点的右子树递归合并即可, 当合并的两个点有一个点不存在。即上一层没有右儿子,直接把这个点接到上一层点上,做其右儿子就好。

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 1100000;int ls[N], rs[N], dis[N], val[N], fa[N], Kill[N];int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}int merge(int x, int y) { if((!x)|(!y)) return x+y; if(val[x] > val[y]) swap(x, y); rs[x] = merge(rs[x], y); if(dis[ls[x]] < dis[rs[x]]) swap(ls[x], rs[x]); dis[x] = dis[rs[x]] + 1; return x; }int main() { int n, m; scanf("%d", &n); for(int i = 1; i <= n; i ++ ) scanf("%d", &val[i]), fa[i] = i; scanf("%d", &m); while(m -- ) { char opt[3]; scanf("%s", opt); if(opt[0] == 'M') { int x, y; scanf("%d%d", &x, &y); if(Kill[x] | Kill[y]) continue; int dx = find(x), dy = find(y); if(dx != dy) fa[dx] = fa[dy] = merge(dx, dy); } else { int x; scanf("%d", &x); if(Kill[x]) { puts("0"); continue; } int dx = find(x); printf("%d\n", val[dx]); fa[dx] = fa[ls[dx]] = fa[rs[dx]] = merge(ls[dx], rs[dx]); Kill[dx] = 1; } }}