mydcwfy's Blog

LOJ3728 [SNOI2022]军队

Posted on
Symbols count in article: 3.3k Reading time ≈ 7 mins.

怎么省选题也出 lxl 的各种分块啊？

题意：给定 $n$ 个物品，每个物品有一个颜色和权值，有三种操作：将 $[l, r]$ 所有颜色为 $x$ 的变为颜色 $y$；将 $[l, r]$ 所有颜色为 $x$ 的权值加 $v$；询问 $[l, r]$ 的区间和。$n, m\leq 2.5\times 10 ^ 5$，6s，允许离线。

显然一眼 lxl Ynoi 题目，估计是没有 $\text{poly}\log$，考虑分块。

我们对于当前块维护一个并查集，用来维护每一个点的颜色是什么。

大概思路就是整块直接把当前并查集颜色 $x$ 代表的根连到 $y$ 上，然后加的时候直接加在根上即可，时间复杂度都是 $O(\alpha(n))$ 单块。散块直接暴力处理，把所有并查集重构一遍，复杂度 $O(\sqrt n)$ 的。

然后主要是坑点很多，下面讲几个：

  1. 合并的时候注意我们不能直接把 $x$ 代表的根连到 $y$ 上，因为 $x, y$ 的标记可能会发生混乱。新建一个节点，当作 $y$ 的新根，然后 $x, y$ 的父亲都设为新建节点，新建节点注意也要设置颜色。另外，$x$ 的根应该赋为空。
  2. 在加的时候，注意使用并查集，我们其实是在边上加权值的，点上加会出错，所以我们再新建一个节点，把原来的节点加上变化权值，这样这个的意义就是原来节点到新根的路径加了一个权值。
  3. 暴力重构的时候注意清空问题。可行的办法是把所有遇到的颜色全部记录下来，把这些位置清空。至于节点清空可以要一个点清空一个点，这样不会导致复杂度退化。
  4. 注意到每一块都要建一个大小 $O(n)$ 的并查集，于是空间复杂度 $O(n\sqrt n)$，然后还因为中间多建点，至少需要开 3 倍空间，这样很容易导致 MLE，所以我们机房的神仙就好像一直调块长。正确的做法是由于允许离线，把每块离线处理，这样就可以做到线性空间，不过没有了强制在线。但其实数据几乎只需要多开点即可，我开始忘开 3 倍空间结果只有满数据没过……
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
void solve(int l, int r)
{
    // std::cout << "Start Solve " << l << ' ' << r << '\n';
    LL totval = 0;
    std::vector<int> all(C);
    for (int i = 0; i < C; ++ i) all[i] = i + 1;
    auto pushdown = [&]() {
        for (int i = l; i <= r; ++ i)
            col[i] = id[find(i)], a[i] = val[i];
        /*printf("After Pushdown\n");
        for (int i = l; i <= r; ++ i) printf("%d %lld\n", col[i], val[i]);*/
    };
    auto rebuild = [&]() {
        tot = n, totval = 0;
        for (int c : all) rt[c] = 0;
        all.clear();
        for (int i = l; i <= r; ++ i)
        {
            if (!rt[col[i]]) id[rt[col[i]] = ++ tot] = col[i], f[tot] = tot, val[tot] = sz[tot] = 0;
            f[i] = rt[col[i]], val[i] = a[i], sz[rt[col[i]]] ++, totval += a[i];
            all.push_back(col[i]);
        }
    };
    rebuild();
    for (int i = 1; i <= Q; ++ i)
    {
        if (eve[i].l > r || eve[i].r < l) continue;
        if (eve[i].op == 1) {
            if (eve[i].l <= l && eve[i].r >= r) {
                int x = eve[i].x, y = eve[i].y;
                if (!rt[x]) continue;
                // std::cout << "Change " << x << ' ' << y << '\n';
                all.push_back(x), all.push_back(y);
                x = find(rt[x]);
                ++ tot, f[tot] = tot, val[tot] = sz[tot] = 0, id[tot] = y;
                if (rt[y]) f[rt[y]] = tot, sz[tot] += sz[rt[y]];
                f[x] = rt[y] = tot, sz[tot] += sz[x], rt[id[x]] = 0;
            } else {
                pushdown();
                for (int j = std::max(eve[i].l, l), ed = std::min(eve[i].r, r); j <= ed; ++ j)
                    if (col[j] == eve[i].x) col[j] = eve[i].y;
                rebuild();
            }
        } else if (eve[i].op == 2) {
            if (eve[i].l <= l && eve[i].r >= r) {
                if (!rt[eve[i].x]) continue;
                all.push_back(eve[i].x);
                int x = find(rt[eve[i].x]);
                ++ tot, f[tot] = tot, val[tot] = sz[tot] = 0;
                val[x] += eve[i].y, totval += (LL) sz[x] * eve[i].y, rt[eve[i].x] = tot;
                f[x] = tot, sz[tot] = sz[x], id[tot] = eve[i].x;
            } else {
                pushdown();
                for (int j = std::max(eve[i].l, l), ed = std::min(eve[i].r, r); j <= ed; ++ j)
                    if (col[j] == eve[i].x) a[j] += eve[i].y;
                rebuild();
            }
        } else {
            if (eve[i].l <= l && eve[i].r >= r) eve[i].res += totval;
            else {
                for (int j = std::max(eve[i].l, l), ed = std::min(eve[i].r, r); j <= ed; ++ j)
                    find(j), eve[i].res += val[j];
            }
        }
    }
}

int main()
{
    // freopen("military.in", "r", stdin);
    // freopen("military.out", "w", stdout);
    read(n, Q, C);
    for (int i = 1; i <= n; ++ i) read(a[i]);
    for (int i = 1; i <= n; ++ i) read(col[i]);
    for (int i = 1; i <= Q; ++ i)
    {
        read(eve[i].op, eve[i].l, eve[i].r);
        if (eve[i].op != 3) read(eve[i].x, eve[i].y);
    }
    int B = std::sqrt(n) + 1;
    for (int l = 1, r; l <= n; l = r + 1) solve(l, r = std::min(l + B - 1, n));
    for (int i = 1; i <= Q; ++ i)
        if (eve[i].op == 3) printf("%lld\n", eve[i].res);
    return 0;
}