自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:32:22，当前版本为作者最后更新于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$ 在操作后的形态。
• $pos_i$ 表示 原 位置 $i$ 的 现 位置。
• $rev_i$ 表示 现 位置 $i$ 的 原 位置。
• $add_i$ 表示 现 位置 $i$ 上的数被查询了多少次。
• 当右端点右移 $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;
}