UOJ14 【UER #1】DZY Loves Graph 题解

题意：

cxy 开始有 \(n\) 个点，现在她对这 \(n\) 个点进行了 \(m\) 次操作，对于第 \(i\) 个操作 (从 \(1\) 开始编号) 有可能的三种情况：

Add a b：表示在 \(a\) 与 \(b\) 之间连了一条长度为 \(i\) 的边 (注意，\(i\) 是操作编号)。保证 \(1\le a,b \le n\) 。

Delete k：表示删除了当前图中边权最大的 \(k\) 条边。保证 \(k\) 一定不会比当前图中边的条数多。

Return：表示撤销第 \(i−1\) 次操作。保证第 \(1\) 次操作不是 Return 且第 \(i−1\) 次不是 Return 操作。

请你在每次操作后告诉 cxy 当前图的最小生成树边权和。如果最小生成树不存在则输出 \(0\)。

输入格式：

第一行包含两个正整数 \(n,m (n\le 3\times 10^5,m\le 5\times 10^5)\) 。表示有 \(n\) 个点和 \(m\) 个操作。

接下来 \(m\) 行每行描述一个操作。

输出格式：

对于每一个操作，输出一行一个整数，表示当前最小生成树边权和。

先考虑不带撤销操作的情况

操作1：

由于边的权值为 \(i\) ，而 \(i\) 是递增的，因此这个过程可以看作 \(\text{Kruskal}\) 加边的过程。

操作2：

对于并查集的撤销合并操作，我们一般采用按秩合并维护其复杂度。

撤销合并的方式很简单，直接 sz[f[x]]-=sz[x],f[x]=x 即可。

同时，因为要删 \(k\) 条边（显然是新加入的 \(k\) 条）

所以我们还要维护一个时间戳，记录当前以及历史添加的边。

实际上，我们还需要维护历史的最小生成树大小和边数，原因见下文。

然后考虑带撤销操作的情况

操作3：

考虑每次在处理第 \(i\) 个操作时，先把 \(i+1\) 的操作读进来，以确定是否要直接删除

撤销操作1，直接删就好。
撤销操作2，意味着我们刚刚的删除要撤销。

这个比较麻烦，并且复杂度是不对的。

反过来，我们在每次操作2时，判断下一个是不是操作3

如果是，直接输出加入最新的 \(k\) 条边前的答案，这个是 \(O(1)\) 的

这也是为什么我们要维护「历史的最小生成树大小和边数」。
否则，暴力删除 \(k\) 条边。

这样每条边最多被删除一次

时间复杂度 \(\mathcal{O}((n+m)\log n)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(3e5+15))
#define M ((int)(5e5+15))

int n,m,tim,f[N],sz[N],hist[M],cnt[M],mst[M];
void init(int n){for(int i=1; i<=n; i++) f[i]=i,sz[i]=1;}
int find(int x){return f[x] == x ? x : find(f[x]);}
void merge(int u,int v,int wt)
{
    int x=find(u), y=find(v);
    if(x == y)
    {
        hist[++tim] = 0;
        cnt[tim] = cnt[tim-1];
        mst[tim] = mst[tim-1];
    }else
    {
        if(sz[x] > sz[y]) swap(x,y);
        f[x] = y; sz[y] += sz[x];
        hist[++tim] = x;
        cnt[tim] = cnt[tim-1] + 1;
        mst[tim] = mst[tim-1] + wt;
    }
}
void cancel(int T)
{
    for(int x; tim > T; --tim)
        x=hist[tim], sz[f[x]]-=sz[x],f[x]=x;
}
void print(int T)
{
    cout << (cnt[T] == n-1 ? mst[T] : 0) << '\n';
}
char getQ(int i)
{
    static char op[9];
    if(i == m) return 0;
    cin >> op; return op[0];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m; int op=getQ(0); init(n);
    for(int i=1,u,v; i<=m; i++)
    {
        if(op == 'A')
        {
            cin >> u >> v; merge(u,v,i); print(tim);
            if((op = getQ(i)) == 'R') cancel(tim - 1);
        }
        else if(op == 'D')
        {
            cin >> v; print(tim-v);
            if((op = getQ(i)) != 'R') cancel(tim - v);
        }
        else {print(tim); op=getQ(i);}
    }
    return 0;
}