P8097 [USACO22JAN] Farm Updates G

· · 题解

*P8097 [USACO22JAN] Farm Updates G

相比于官方线性 sol，我的做法仅供大家看个乐子。

加边删边考虑线段树分治，用可持久化并查集维护每个叶子结点的联通情况。注意到我们仅在活跃农场之间加边，故若一个农场变得不相关，则它永远不会再相关，因此具有可二分性。对每个农场二分答案即可。

如何判断一个农场与一个活跃农场相连？考虑将农场重标号为其被停用的次序，即第 i 个被停用的农场标号为 i，则对于当前农场 p 和二分的时刻 t，设此时已经有 d_t 个农场被停用，那么 p 与活跃农场相连等价于 p 所在连通块节点标号最大值 > d_t。可持久化并查集可以维护标号最大值。

一次查询的复杂度为 \log ^ 2 n，因此时间复杂度 \mathcal{O}(n\log n\log ^ 2 Q)，空间复杂度 \mathcal{O}(n\log n\log Q)。时空双双爆炸。

由于询问离线，考虑 整体二分。即对于 时刻区间 [0, Q]，设其中点为 m，线段树分治到叶子结点时刻 m，查询所有农场是否相关，将不相关的农场丢到 时刻区间 [0, m - 1]，相关的农场丢到时刻区间 [m, Q]。再向两侧递归。

线段树上需要从时刻 p\to q，就从 p 向上跑到 p, q 在线段树上的 LCA，再向下跑到叶子结点 q。向上跑的时候离开一个节点要撤销该节点所存储的边的贡献，向下跑的时候加入一个节点要算上该节点所存储的边的贡献，类比普通线段树分治。

乍一看，在分治线段树上的移动复杂度似乎不可接受，但是类似决策单调性分治在贡献难算时的复杂度分析， 线段树上每个节点均只会被经过常数次。配合可撤销并查集，视 n, q 同阶，时间复杂度 \mathcal{O}(n \log ^ 2 n)，空间复杂度 \mathcal{O}(n\log n)。比线性劣了很多，但大概启发性在于将线段树分治和整体二分相结合（可能已经烂大街了吧？从来没见过这个套路，赛时还分析了好长时间复杂度，是我才疏学浅了）。

#include <bits/stdc++.h>
using namespace std;

#define pii pair <int, int>
const int N = 2e5 + 5;
int n, q, num[N], pos[N], ans[N];
int p[N], x[N], y[N]; char op[N];
vector <pii> ed[N << 2];
void build(int l, int r, int x) {
    if(l == r) return pos[l] = x, void();
    int m = l + r >> 1;
    build(l, m, x << 1), build(m + 1, r, x << 1 | 1);
}
void modify(int l, int r, int ql, int qr, int x, pii v) {
    if(ql <= l && r <= qr) return ed[x].push_back(v), void();
    int m = l + r >> 1;
    if(ql <= m) modify(l, m, ql, qr, x << 1, v);
    if(m < qr) modify(m + 1, r, ql, qr, x << 1 | 1, v);
}

struct dat {int u, v, omx;};
struct dsu {
    int fa[N], sz[N], mx[N];
    int find(int x) {return fa[x] == x ? x : find(fa[x]);}
    void init() {for(int i = 1; i <= n; i++) fa[i] = i, mx[i] = i, sz[i] = 1;}
    dat merge(int u, int v) {
        if(sz[u] < sz[v]) swap(u, v);
        dat ret = {u, v, mx[u]};
        sz[u] += sz[v], fa[v] = u;
        if(mx[v] > mx[u]) mx[u] = mx[v];
        return ret;
    } void undo(dat d) {
        sz[d.u] -= sz[d.v], fa[d.v] = d.v, mx[d.u] = d.omx;
    }
} f;

int cur = 1, lg[N << 2], top, stc[N];
dat oper[N];
bool ances(int anc, int p) {
    if(lg[anc] > lg[p]) return 0;
    return anc == (p >> lg[p] - lg[anc]);
}
void move(int aim) {
    while(!ances(cur, aim)) {
        assert(cur != 1);
        while(stc[top] == cur) f.undo(oper[top]), top--;
        cur >>= 1;
    } while(cur != aim) {
        if(ances(cur << 1, aim)) cur <<= 1;
        else cur = cur << 1 | 1;
        for(pii it : ed[cur]) {
            int u = f.find(it.first), v = f.find(it.second);
            if(u == v) continue;
            stc[++top] = cur, oper[top] = f.merge(u, v);
        }
    }
}
void solve(int l, int r, vector <int> &arr) {
    if(arr.empty()) return;
    if(l == r) {for(int it : arr) ans[it] = l; return;}
    int m = l + r + 1 >> 1;
    move(pos[m]);
    vector <int> left, right;
    for(int it : arr) {
        int val = f.mx[f.find(it)];
        if(val <= num[m]) left.push_back(it);
        else right.push_back(it);
    } solve(l, m - 1, left), solve(m, r, right);
}

int main() {
    cin >> n >> q, f.init(), build(1, q, 1);
    for(int i = 2; i < N << 2; i++) lg[i] = lg[i >> 1] + 1;
    for(int i = 1, cur = 0, ed = 0; i <= q; i++) {
        static int st[N]; cin >> op[i] >> x[i];
        if(op[i] == 'A') cin >> y[i], st[++ed] = i;
        if(op[i] == 'D') p[x[i]] = ++cur; num[i] = cur;
        if(i == q) {
            for(int j = 1; j <= n; j++) if(!p[j]) p[j] = ++cur;
            for(int j = 1; j <= q; j++)
                if(op[j] == 'A') x[j] = p[x[j]], y[j] = p[y[j]];
                else if(op[j] == 'R') modify(1, q, st[x[j]], j - 1, 1, {x[st[x[j]]], y[st[x[j]]]}), st[x[j]] = -1;
            for(int j = 1; j <= ed; j++) if(st[j] != -1)
                modify(1, q, st[j], q, 1, {x[st[j]], y[st[j]]});
        }
    } for(pii it : ed[1]) {
        int u = f.find(it.first), v = f.find(it.second);
        if(u == v) continue;
        stc[++top] = cur, oper[top] = f.merge(u, v);
    } vector <int> arr;
    for(int i = 1; i <= n; i++) arr.push_back(i);
    solve(0, q, arr);
    for(int i = 1; i <= n; i++) cout << ans[p[i]] << "\n";
    return 0;
}