P8097 [USACO22JAN] Farm Updates G 题解

· · 题解

给出一张 n 个点的无向图，刚开始所有点的权值都是 1，没有边。共有 q 次操作，操作分以下三种：

  • R x 将一个点的权值变为 0。
  • A x y 在两点 x,y 之间连一条边，保证 x,y 的权值均为 1。
  • D e 删除加入的第 e 条边，边从 1 开始编号。

如果一个点权值为 1 或与权值为 1 的点连通，则定义这个点是「关联的」。对于每个点求最大的 i(0\le i\le q)，使得在这次操作后该点是「关联的」。(1\le n\le 10^5,1\le q\le 2\times10^5)

分析一波这些操作，我们能发现第二个操作似乎并不会改变每个点的关联性。注意到一个连通块内的点关联性都是相同的，而二操作相当于合并两个均为「关联的」的连通块，当然不会改变连通性。所以现在我们要维护的东西就变为了单点修改和删边。显然加边更好处理，所以考虑改成倒序处理。

我们来分析一下倒序的这些操作。

想一下我们现在的操作，遍历一个连通块，合并两个连通块，而这些一个并查集就可以做到。而倒序操作从非「关联的」变为「关联的」的时间点的上一个时间，就是最终的答案。（注意一个点一旦变为「关联的」就不会再变回去了，因为上面的操作并不会影响到这一点）

实现时不要忘了倒序操作前加入在最后没有删除的边。时间复杂度是均摊的 \mathcal{O}(n+q)。

#include <cstdio>
#include <vector>
#include <cstdlib>
const int N = 2e5 + 10; int f[N]; std::vector<int> vec[N];
struct query{ int op, x; }q[N]; int ans[N], vis[N];
struct edge{ int x, y; }e[N]; int tp, del[N];
int getf(int x) { return x == f[x] ? x : f[x] = getf(f[x]); }
inline void link(int u, int v, int now)
{
    u = getf(u), v = getf(v); if (u == v) return ;
    if ((!vis[u]) ^ (!vis[v]))
    {
        if (!vis[u]) for (auto x : vec[u]) vis[x] = now;
        else for (auto x : vec[v]) vis[x] = now;
    }
    if (vec[u].size() > vec[v].size()) { f[v] = u; for (auto x : vec[v]) vec[u].push_back(x); }
    else { f[u] = v; for (auto x : vec[u]) vec[v].push_back(x); }
}
int main()
{
    char op[5]; int x, y, n, Q; scanf("%d%d", &n, &Q);
    for (int i = 1; i <= n; ++i) f[i] = i, vis[i] = Q, vec[i].push_back(i);
    for (int i = 1; i <= Q; ++i)
    {
        scanf("%s", op);
        if (op[0] == 'A') scanf("%d%d", &x, &y), e[++tp].x = x, e[tp].y = y;
        else scanf("%d", &x), q[i].op = op[0] == 'D' ? 1 : 2, q[i].x = x;
    }
    for (int i = 1; i <= Q; ++i) 
        if (q[i].op == 1) vis[q[i].x] = 0;
        else del[q[i].x] = 1;
    for (int i = 1; i <= tp; ++i) if (!del[i]) link(e[i].x, e[i].y, Q);
    for (int i = Q; i >= 1; --i)
    {
        if (!q[i].op) continue;
        if (q[i].op == 1)
        {
            int u = getf(q[i].x);
            if (!vis[u]) for (auto x : vec[u]) vis[x] = i - 1;
        }
        else link(e[q[i].x].x, e[q[i].x].y, i - 1);
    }
    for (int i = 1; i <= n; ++i) printf("%d\n", vis[i]);    
    return 0;
}