题目描述

难度分:$2600$

输入$n(1 \leq n \leq 2 \times 10^5)$，$m(1 \leq m \leq 3 \times 10^5)$，$q(1 \leq q \leq 5 \times 10^5)$和一个$1$~$n$的排列$p$。

有一个$n$个点$m$条边的图，点$v$的点权为$p[v]$。然后输入$m$条边。节点编号从$1$开始，不含重边和自环。

然后输入$q$个询问，格式如下：

• 1 v：输出$v$所在连通块的最大点权，然后把这个点权改成$0$。
• 2 i：删除输入的第$i$条边。$i$从$1$开始。保证$i$之前没有被删除过。

输入样例

5 4 6
1 2 5 4 3
1 2
2 3
1 3
4 5
1 1
2 1
2 3
1 1
1 2
1 2

输出样例

5
1
2
0

算法

启发式合并

这个题刚一看到就想反着来做，这样删边就变成了加边，用并查集维护非常方便。但问题就在于操作$1$的点权赋$0$操作，这个操作我想了很久都没想到怎么高效地倒着操作，所以再次宣告了周五开茶失败。看了一下题解区，大部分是$DFS$序+线段树，有个基本考点就是“重构树”，这玩意儿没学过，我也确实想不到。不过除了这种解法，还看到有一个倒着做启发式合并的思路我是想过的，只是没有考虑全导致没能开出来，所以着重学习了这个解法。

构建一个映射$group$，它表示“节点 $\rightarrow$ 这个节点所在连通块的全部点权”。遍历边集，忽略掉所有待删除的边，利用启发式合并构建$group$映射，形成整棵树（可能是森林）。然后按照以下步骤来做：

1. 倒着处理每个询问，当遇到删边操作时（操作$2$），利用启发式合并更新$group$映射，把这条边加入到森林中。
2. 遍历$i \in [1,n]$，把$group[i]$中的点权排好序。并构建一个$root$数组，$root[a[i]]=find(i)$，表示点权$a[i]$属于$find(i)$这个连通分量（$find$是并查集操作）。进行这一步就是为了高效查询最大那个待归零的点权。
3. 最后正着处理每个询问，如果是操作$1$，找到$i$所在连通分量中最大的未归零点权，将其标记$used[group[x].back()]=$true，并从$group[x]$中弹出这个点权。如果是操作$2$，就对$group$进行启发式合并，同时维护$root$数组和并查集的$father$数组$p$。

复杂度分析

时间复杂度

启发式合并每次都会使得集合的大小至少变为原来的两倍，那么最差情况下就是从$1$变成$n$，需要进行$O(log_2n)$这个级别的合并次数。因此遍历边集时的启发式合并时间复杂度为$O(mlog_2n)$；倒序处理询问时的启发式合并时间复杂度为$O(qlog_2n)$；对每个$group[x]$排序，由于排序的元素个数在$O(nlog_2n)$级别，因此这个步骤的时间复杂度为$O(n(log_2n)^2)$。最后再正序处理每个询问，对于每个询问都要进行$O(log_2n)$级别的操作，时间复杂度为$O(qlog_2n)$。

综上，整个算法的时间复杂度为$O((m+q)log_2n+n(log_2n)^2)$

空间复杂度

并查集的$p$数组，$sz$数组都是$O(n)$级别的。边集标记数组$del$是$O(m)$，点集边集数组$used$是$O(n)$。点权所属连通块的数组$root$空间是$O(n)$。最大的瓶颈是映射$group$，由于元素数量是$O(nlog_2n)$，所以空间复杂度是$O(nlog_2n)$。

综上，整个算法的额外空间复杂度为$O(n+m+nlog_2n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010, M = 300010;
int n, m, q, a[N], p[N], sz[N], root[N];
bool del[M], used[N];
vector<int> group[N];

struct Edge {
    int x, y;
} edges[M];

struct Query {
    int opt, id, rx, ry;
} queries[N + M];

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

int query(int x){
    while(group[x].size() && (root[group[x].back()] != x || used[group[x].back()])) group[x].pop_back();
    if(group[x].empty()) return 0;
    int w = group[x].back();
    return group[x].pop_back(), used[w] = 1, w;
}

int main() {
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        group[p[i]=i].push_back(a[i]=x);
        sz[i] = 1;
    }
    for(int i = 1; i <= m; i++) {
        scanf("%d%d", &edges[i].x, &edges[i].y);
    }
    for(int i = 1; i <= q; i++){
        scanf("%d%d", &queries[i].opt, &queries[i].id);
        if(queries[i].opt == 2) {
            del[queries[i].id] = 1;
        }
    }
    for(int i = 1; i <= m; i++){
        if(del[i]) continue;
        int x = find(edges[i].x), y = find(edges[i].y);
        if(x == y) continue;
        if(sz[x] > sz[y]) swap(x, y);
        for(int w: group[x]) {
            group[y].push_back(w);
        }
        p[x] = y, sz[y] += sz[x];
    }
    for(int i = q; i >= 1; i--){
        int x = edges[queries[i].id].x, y = edges[queries[i].id].y;
        if(queries[i].opt == 1 || find(x) == find(y)) continue;
        x = find(x), y = find(y);
        if(sz[x] > sz[y]) swap(x, y);
        queries[i].rx = x;
        queries[i].ry = y;
        p[x] = y;
        sz[y] += sz[x];
        for(int w: group[x]) {
            group[y].push_back(w);
        }
    }
    for(int i = 1; i <= n; i++) {
        sort(group[i].begin(), group[i].end());
        root[a[i]] = find(i);
    }
    for(int i = 1; i <= q; i++){
        if(queries[i].opt == 1) {
            printf("%d\n", query(find(queries[i].id)));
        }else if(queries[i].rx){
            for(int j: group[queries[i].rx]) {
                root[j] = queries[i].rx;
            }
            p[queries[i].rx] = queries[i].rx;
        }
    }
    return 0;
}