比 log 更快的离线区间推平

· · 算法·理论

每日一个小技巧系列，不过不知道这个的也只有我了吧。

问题

现在我们面对着这样一个问题：对给定序列做若干次区间推平，所有推平完成之后进行若干次询问，每次给定一个点询问该点的值。

初步解法

首先，线段树。

但是线段树是 log 的单次复杂度，不够快。这个问题不是一般的区间推平，于是我们可能有更快的解法。

时间倒流

问题的特殊性质就是做完所有推平之后才会有询问。于是考虑将询问离线。

我们发现，如果单次推平的复杂度是 O(\mathrm{len}) ，其中 \mathrm{len} 是推平的区间在最终序列中没有被覆盖的长度，那么均摊的复杂度就是单次常数的。

如果要从这一方面入手，那么就需要知道序列中的哪里没有被覆盖。正向考虑是困难的，于是我们按照询问的时间顺序的逆向考虑问题。

这样一来，当前序列上属于该推平区间的没有被覆盖的区域就是最终留下的区域。

跳过已经被染色的区域

如果我们每次推平时都重复遍历已经被覆盖过的区域，那么复杂度显然就错了。

于是我们维护指针，指向下一个没有被覆盖过的位置。

并查集

很遗憾，直接维护的做法是错的。因为你进行一次推平之后可能要对一个“被覆盖段”内的 O(n) 个元素的指针进行更新。这个复杂度是错误的。

但是我们可以用并查集。将每个被覆盖连续段并到一个集合中，然后维护该集合的左右界等等。

于是就做完了。复杂度 O(n\alpha(n))。

代码

#include <bits/stdc++.h>

using namespace std;
int n, q;
bool covered[1000005];
array<int, 1000005> a, fa, height, r_edge;

struct type_of_op {
    int l, r, x;

    type_of_op(int l, int r, int x) : l(l), r(r), x(x) {}
};

vector<type_of_op> ops;

int find(int x) {
    if (x == fa[x]) {
        return x;
    } else {
        return fa[x] = find(fa[x]);
    }
}

inline void merge(int x, int y) {
    int fx = find(x), fy = find(y);

    if (height[fx] > height[fy]) {
        swap(fx, fy);
    }

    fa[fx] = fy;
    if (height[fx] == height[fy]) {
        height[fy]++;
    }

    r_edge[fy] = max(r_edge[fy], r_edge[fx]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];

        fa[i] = i;
        r_edge[i] = i;
        height[i] = 1;
    }

    for (int i = 0; i < q; ++i) {
        int l, r, x;
        cin >> l >> r >> x;
        ops.emplace_back(l, r, x);
    }

    reverse(ops.begin(), ops.end());

    for (auto [l, r, x]: ops) {
        for (int i = l; i <= r;) {
            if (!covered[i]) {
                a[i] = x;
                covered[i] = true;
                if (covered[i - 1]) {
                    merge(i - 1, i);
                }

                if (covered[i + 1]) {
                    merge(i, i + 1);
                }

                i++;
            } else {
                i = r_edge[find(i)] + 1;
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        cout << a[i] << " ";
    }
    return 0;
}