Visits: 372

CF571D Campus

题意

• 有一个长度为 $n$ 的序列，初始全为 $0$。
• 有两类对下标的集合，初始时每一类各有 $n$ 个集合，编号为 $i$ 的集合里有下标 $i$。
• 一共有 $m$ 个操作，操作有五种：
  1. U x y 将第一类编号为 $y$ 的集合合并到编号为 $x$ 的集合里。
  2. M x y 将第二类编号为 $y$ 的集合合并到编号为 $x$ 的集合里。
  3. A x 将第一类编号为 $x$ 的集合中的所有下标在序列中对应的数加上 $x$ 的集合大小。
  4. Z x 将第二类编号为 $x$ 的集合中的所有下标在序列中对应的数设为 $0$。
  5. Q x 询问序列中下标为 $x$ 的位置上的数。
• $n,m \le 5 \times 10^5$。

题解

如果我们能够利用 M 和 Z 操作求出对于每个询问的位置上次清零的时刻 $t$，那么这个询问的答案就应该是只保留 U 和 A 操作的情况下此时的值减去 $t$ 时刻的值。

那么我们要解决的问题可以分为两步：

1. 利用 M 和 Z 操作求出对于每个询问的位置上次清零的时刻 $t$。
2. 利用 U 和 A 操作求出对于每个询问的位置当前和时刻 $t$ 的值。

将询问离线后，建立 kruskal 重构树，那么这两步就分别相当于在 dfs 序上进行区间赋值和区间加，询问则相当于单点查询，线段树维护即可。

设 $n,m$ 同阶，时间复杂度为 $\mathcal O(n \log n)$。

代码

const int N = 5e5 + 7;
int n, m, a[N];
char s[N], c[3];
vector<pi> q[N];
ll ans[N];

struct kruskal0 {
    int f[N*2], l[N*2], r[N*2], num, tot;
    vi e[N*2];
    struct T {
        int l, r, s;
    } t[N*8];
    inline void init() {
        for (int i = 1; i <= n; i++) f[i] = i;
        tot = n;
    }
    int get(int x) {
        return x == f[x] ? x : (f[x] = get(f[x]));
    }
    inline int add(int x, int y) {
        e[++tot].pb(x = get(x)), e[tot].pb(y = get(y));
        return f[x] = f[y] = f[tot] = tot;
    }
    void dfs(int x) {
        l[x] = ++num;
        for (auto y : e[x]) dfs(y);
        r[x] = num;
    }
    void build(int p, int l, int r) {
        t[p].l = l, t[p].r = r;
        if (l == r) return;
        build(ls, l, md), build(rs, md + 1, r);
    }
    inline void prework() {
        for (int i = 1; i <= tot; i++) if (get(i) == i) dfs(i);
        build(1, 1, tot);
    }
    inline void spd(int p) {
        if (t[p].s) t[ls].s = t[rs].s = t[p].s, t[p].s = 0;
    }
    void set(int p, int l, int r, int x) {
        if (t[p].l >= l && t[p].r <= r) return t[p].s = x, void();
        spd(p);
        if (l <= md) set(ls, l, r, x);
        if (r > md) set(rs, l, r, x);
    }
    inline void set(int i) {
        set(1, l[a[i]], r[a[i]], i);
    }
    int asks(int p, int x) {
        if (t[p].l == t[p].r) return t[p].s;
        spd(p);
        return asks(x <= md ? ls : rs, x);
    }
    inline int asks(int i) {
        return asks(1, l[a[i]]);
    }
} t0;

struct kruskal1 {
    int f[N*2], s[N*2], l[N*2], r[N*2], num, tot;
    vi e[N*2];
    struct T {
        int l, r;
        ll a;
    } t[N*8];
    inline void init() {
        for (int i = 1; i <= n; i++) f[i] = i;
        tot = n;
    }
    int get(int x) {
        return x == f[x] ? x : (f[x] = get(f[x]));
    }
    inline int add(int x, int y) {
        e[++tot].pb(x = get(x)), e[tot].pb(y = get(y));
        return f[x] = f[y] = f[tot] = tot;
    }
    void dfs(int x) {
        l[x] = ++num, s[x] = x <= n;
        for (auto y : e[x]) dfs(y), s[x] += s[y];
        r[x] = num;
    }
    void build(int p, int l, int r) {
        t[p].l = l, t[p].r = r;
        if (l == r) return;
        build(ls, l, md), build(rs, md + 1, r);
    }
    inline void prework() {
        for (int i = 1; i <= tot; i++) if (get(i) == i) dfs(i);
        build(1, 1, tot);
    }
    inline void spd(int p) {
        if (t[p].a) t[ls].a += t[p].a, t[rs].a += t[p].a, t[p].a = 0;
    }
    void add(int p, int l, int r, int x) {
        if (t[p].l >= l && t[p].r <= r) return t[p].a += x, void();
        spd(p);
        if (l <= md) add(ls, l, r, x);
        if (r > md) add(rs, l, r, x);
    }
    inline void add(int x) {
        add(1, l[x], r[x], s[x]);
    }
    ll aska(int p, int x) {
        if (t[p].l == t[p].r) return t[p].a;
        spd(p);
        return aska(x <= md ? ls : rs, x);
    }
    inline ll aska(int x) {
        return aska(1, l[x]);
    }
} t1;

int main() {
    rd(n), rd(m), t1.init(), t0.init();
    for (int i = 1, x; i <= m; i++) {
        rds(c, x), s[i] = c[1], rd(a[i]);
        switch (s[i]) {
            case 'U' : rd(x), a[i] = t1.add(a[i], x); break;
            case 'M' : rd(x), a[i] = t0.add(a[i], x); break;
            case 'A' : a[i] = t1.get(a[i]); break;
            case 'Z' : a[i] = t0.get(a[i]); break;
        }
    }
    t1.prework(), t0.prework();
    for (int i = 1; i <= m; i++)
        switch (s[i]) {
            case 'Z' : t0.set(i); break;
            case 'Q' : q[t0.asks(i)].pb(mp(a[i], i)); break;
        }
    for (int i = 1; i <= m; i++)
        switch (s[i]) {
            case 'A' : t1.add(a[i]); break;
            case 'Z' : for (pi o : q[i]) ans[o.se] -= t1.aska(o.fi); break;
            case 'Q' : ans[i] += t1.aska(a[i]); break;
        }
    for (int i = 1; i <= m; i++) if (s[i] == 'Q') print(ans[i]);
    return 0;
}