P7708「Wdsr-2.7」八云蓝自动机 Ⅰ

Alex_Wei · 2021-10-04 00:57:29 · 题解

*X. P7708「Wdsr-2.7」八云蓝自动机Ⅰ。

摘自 根号算法 Part.3 莫队 例题 X.

一道莫队好题。本题最有价值的地方在于对单点修改的转化，以及对交换两个数的处理：维护原来每个位置现在的位置，以及现在每个位置原来的位置。

注意到单点修改并不方便实现，将其转化为交换两个数。对于 a_x\gets k，我们新建 a_c = k，并将其看做 a_x 与 a_c 交换。这一步非常巧妙，因为它消灭了单点修改这一类麻烦的操作。

多次询问一段区间的操作结果，一般使用莫队实现。因此，考虑区间在伸缩时需要维护哪些信息。为了支持在操作序列最前面加入交换两个数的操作，可以想到维护：

• 序列 a 在操作后的形态。
• 当右端点右移 r - 1\to r 时：
  • 若第 r 个操作是交换 x, y，则交换 a_x 和 a_y，rev_x 和 rev_y，pos_{rev_x} 和 pos_{rev_y}。
  • 若第 r 个操作是查询 x，则令 ans\gets ans + a_x，add_x\gets add_x + 1。
• 当左端点左移 l+1\to l 时：
  • 若第 l 个操作是交换 x,y，注意我们相当于 交换原位置 上的两个数，因此对答案有影响。先交换 a_{pos_x} 和 a_{pos_y}，rev_{pos_x} 和 rev_{pos_y}，pos_x 和 pos_y。由于交换原位置上的两个数并不影响现位置被查询的数的次数（因为我们已经交换了 a_{pos_x} 和 a_{pos_y}，或者说 a 和 add 当中只要交换一个即可描述本次操作，多交换反而会让答案错误），因此答案加上 交换后 的 (a_{pos_x} - a_{pos_y})(add_{pos_x} - add_{pos_y})，相当于把每个数原来的贡献减掉，加上新的贡献。
  • 若第 l 个操作是查询 x，则令 ans\gets ans + a_{pos_x}，add_{pos_x} \gets add_{pos_x} + 1。

右端点左移和左端点右移的情况分别与上述两种情况相似，仅是符号相反，此处不再赘述。时间复杂度 \mathcal{O}(n\sqrt n)。

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

#define uint unsigned int
const int N = 4e5 + 5, B = 444;
int n, m, q, op[N], x[N], y[N], a[N];
uint cur, ans[N], add[N], pos[N], rev[N];
struct query {
    int l, r, blk, id;
    bool operator < (const query &v) const {
        return blk != v.blk ? blk < v.blk : blk & 1 ? r > v.r : r < v.r;
    }
} c[N];
int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= m; i++) {
        scanf("%d %d", &op[i], &x[i]);
        if(op[i] == 1) scanf("%d", &a[++n]), y[i] = n, op[i] = 2;
        else if(op[i] == 2) scanf("%d", &y[i]);
    }
    for(int i = 1; i <= n; i++) pos[i] = rev[i] = i;
    cin >> q;
    for(int i = 1; i <= q; i++) {
        scanf("%d %d", &c[i].l, &c[i].r);
        c[i].blk = c[i].l / B, c[i].id = i;
    }
    sort(c + 1, c + q + 1);
    for(int i = 1, l = 1, r = 0; i <= q; i++) {
        while(r < c[i].r) {
            r++;
            if(op[r] == 2) {
                swap(a[x[r]], a[y[r]]);
                swap(rev[x[r]], rev[y[r]]);
                swap(add[x[r]], add[y[r]]);
                swap(pos[rev[x[r]]], pos[rev[y[r]]]);
            } else add[x[r]]++, cur += a[x[r]];
        }
        while(l > c[i].l) {
            l--;
            if(op[l] == 2) {
                swap(pos[x[l]], pos[y[l]]);
                swap(a[pos[x[l]]], a[pos[y[l]]]);
                swap(rev[pos[x[l]]], rev[pos[y[l]]]);
                cur += add[pos[x[l]]] * (a[pos[x[l]]] - a[pos[y[l]]]);
                cur += add[pos[y[l]]] * (a[pos[y[l]]] - a[pos[x[l]]]);
            } else add[pos[x[l]]]++, cur += a[pos[x[l]]];
        }
        while(r > c[i].r) {
            if(op[r] == 2) {
                swap(a[x[r]], a[y[r]]);
                swap(rev[x[r]], rev[y[r]]);
                swap(add[x[r]], add[y[r]]);
                swap(pos[rev[x[r]]], pos[rev[y[r]]]);
            } else add[x[r]]--, cur -= a[x[r]];
            r--;
        }
        while(l < c[i].l) {
            if(op[l] == 2) {
                cur -= add[pos[x[l]]] * (a[pos[x[l]]] - a[pos[y[l]]]);
                cur -= add[pos[y[l]]] * (a[pos[y[l]]] - a[pos[x[l]]]);
                swap(pos[x[l]], pos[y[l]]);
                swap(a[pos[x[l]]], a[pos[y[l]]]);
                swap(rev[pos[x[l]]], rev[pos[y[l]]]);
            } else add[pos[x[l]]]--, cur -= a[pos[x[l]]];
            l++;
        }
        ans[c[i].id] = cur;
    }
    for(int i = 1; i <= q; i++) printf("%u\n", ans[i]);
    return 0;
}