题解 CF911G 【Mass Change Queries】

逆流之时 · 2020-04-07 10:21:11 · 题解

老师讲这道题时用的是线段树。一段时间后我从零开始做这道题时，想了 1h 多线段树的 push_down() 函数怎么写才能去掉 100 这个常数，然后才发现这题可以直接分块碾过去。自己很喜欢的数据结构竟然没有第一时间想到。

这题使用分块思路还是很简单的。

由于不能暴力修改，而普通的数组或者并查集又不能维护数与数之间的映射关系。所以我们为了使用延迟标记维护数的映射关系，需要考虑更加暴力的延迟标记维护方法：vector 启发式合并。

然后因为这个东西放到线段树上维护会常数巨大且非常难维护，所以我们考虑分块。

设最大值为 size，分块大小为 maxn，先对于每一块开 100 个 vector，然后使用两个函数：

• merge() 即对于修改 l r x y 按秩合并同一块中的 x, y 对应的两个 vector，时间复杂度均摊 O(\log size)，且常数较小，一般跑不满。
• assign() 即对于一整块，把 vector 维护的数的映射关系下传到单个数上，然后把 vector 恢复原状，时间复杂度 O(maxn + size)。初始时 vector 中 v_{i, j} = \{j\}。总的时间复杂度为每次修改 \log size \frac{n}{maxn} + maxn + size，最终对每一块 assign() 一遍的时间复杂度为 O(n + \frac{n}{maxn} \times size)。

由于分块常数小，虽然这题使用分块的时间复杂度很大，为 O(n \sqrt n \log n)，但实际上使用分块碾过去毫无压力，maxn = \sqrt n 时用了 2.11min，最慢的一个点 1825ms，还算正常；而使用最优分块大小 maxn = \sqrt {n \log size} + 1 时只用 1.58min，最慢的点 935ms。总用时大约是一般线段树用时的 3 倍。

如果实在要将这种方法卡到时间复杂度上界，可以考虑对这种方法进行更详细的时间复杂度势能分析，以找到构造数据的方法：

设一开始所有块都处于初态；

• merge()：每一轮修改中，可以对一块消耗 O(\log size) 的时间复杂度。如果对初态下的同一块使用了 size 次 merge()，则该块到达终态，不能再消耗时间复杂度（不过遍历到这一块的时间复杂度仍为 O(1)）。每一轮可以对任意块使用 merge()（实际为连续的若干块，不过这里可以不考虑）。
• assign()：每一轮修改中，可以使一块恢复到初态。每一轮可以对最多 2 块使用 assign()。

所以如果要卡这种方法，可以设计这样的数据：先不断对区间 1 n 执行可以将按秩合并卡到 O(\log n) 的合并操作，然后再对区间 [maxn * k + 1, maxn * k + 2 * maxn] 执行修改，这样就可以使用 \frac{n}{2 \times maxn} 次操作使其恢复终态。

当然，以上的数据构造方法不能在实际情况下保证卡掉分块。因为分块 3s 跑 n = 200000 的数据一般是可以过的，并且分块可以微调块大小，或者直接使块大小根据随机数波动，使别人根本没法卡。

这题里很多地方需要考虑 (i + 1) * maxn <= n 这样的边界情况，我还因此 Wa on 114 了几次。同时 CF 的 hack 机制非常毒瘤，导致 n = 1, maxn = \sqrt {n \log n} 时会 RE，需要将 maxn 改为 maxn = \sqrt {n \log n} + 1（不过设为 maxn = \sqrt {n \log size} + 1 时不用考虑）。

#include<cstdio>
#include<cmath>
#include<vector>
int n, q, maxn;
int a[200005];
std::vector<int> v[1900][105];
inline void merge(std::vector<int> &v1, std::vector<int> &v2) {
    if (v1.size() < v2.size()) std::swap(v1, v2);
    v1.insert(v1.end(), v2.begin(), v2.end());
    v2.clear();
}
inline void assign(int i, int x, int y, int l, int r) {
    static int vis[105] = {};
    if ((i + 1) * maxn <= n) {
        for (int j = 1; j <= 100; j++) {
            for (int k : v[i][j]) vis[k] = j;
            v[i][j].clear();
            v[i][j].push_back(j);
        }
        for (int j = i * maxn; j < (i + 1) * maxn; j++) a[j] = vis[a[j]];
    }
    for (int j = l; j < r; j++)
        if (a[j] == x) a[j] = y;
}
int main() {
    scanf("%d", &n);
    maxn = sqrt(n * log2(n)) + 1;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; (i + 1) * maxn <= n; i++)
        for (int j = 1; j <= 100; j++) v[i][j].push_back(j);
    for (scanf("%d", &q); q--;) {
        int l, r, x, y, L, R;
        scanf("%d%d%d%d", &l, &r, &x, &y);
        if (x != y) {
            l--;
            L = l / maxn, R = r / maxn;
            if (L != R) {
                assign(L, x, y, l, (L + 1) * maxn);
                for (int i = L + 1; i < R; i++) merge(v[i][y], v[i][x]);
                assign(R, x, y, R * maxn, r);
            } else assign(L, x, y, l, r);
        }
    }
    for (int i = 0; (i + 1) * maxn <= n; i++) assign(i, 0, 0, 0, 0);
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
}