「Summary」2022-08-04 做题记录

莫队 😍😍😍

2022-08-04

$\mathbb{数颜色}$

link

确保我真的会带修莫队

其实询问和查询时分开的。需要记录现在的查询是在哪个修改之后的。
每次的修改都是直接暴力计算贡献。
给一个代码框架。

void add(int x) { add contribution }
void del(int x) { del contribution }

void change(int x) {
	if (the optition can effect in the query) {
		del();
		// reverse the optition
		add();
	} else {
		// reverse the optition
	}
}

siz = pow(n, 2.0 / 3.0);

sort(q + 1, q + 1 + qnum, [](const Query& x, const Query& y) {
	if (block[x.l] != block[y.l]) return x.l < y.l;
	if (block[x.r] != block[y.r]) return x.r < y.r;
	return x.tim < y.tim;
});

for (int i = 1; i <= qnum; i++) {
	while (l < q[i].l) del(l++);
	while (l > q[i].l) add(--l);
	while (r > q[i].r) del(r--);
	while (r < q[i].r) add(++r);
	while (tim < q[i].tim) change(++tim);
	while (tim > q[i].tim) change(tim--);
	ans[q[i].ind] = res;
}

$\mathbb{CF940F}$

link

我不会读题

这个题面真坑，暴力扫就可以过，复杂度在 $\Theta(n ^ {\frac{5}{3}})$ 左右。

$\mathbb{HDU \ 6610}$

link

能过就怪了

考虑他为什么限制交换操作只操作相邻的两个数字，其实很显然，对于操作后只有 $pos$ 位置上的前缀异或和发生改变，并且可以 $\Theta(1)$ 计算。
这个提示我们把交换操作转化成一个单点修改操作，在读入的时候就可以直接模拟一遍，把操作转过来。之后就是维护区间内相同数字的个数就行了。
关于我写错了哪些地方

void change(int x) {
	if (c[x].pos >= l && c[x].pos <= r) {
		- del(x);
		+ del(c[x].pos);
		- swap(c[x].val, pre[x]);
		+ swap(c[x].val, pre[c[x].pos]);
		- add(x);
		+ add(c[x].pos);
	- } else swap(c[x].val, pre[x]);
	+ } else swap(c[x].val, pre[c[x].pos]);
}

sort(q + 1, q + 1 + qnum, [](const Query& x, const Query& y) {
	- if (block[x.l] == block[y.l]) return x.r < y.r;
	- else return block[x.l] < block[y.l];
	+ if (block[x.l] != block[y.l]) return x.l < y.l;
	+ if (block[x.r] != block[y.r]) return x.r < y.r;
	+ return x.tim < y.tim;
});

综上，写代码不过脑子。

$\mathbb{JOISC 2014 Day1 T3「歴史の研究」}$

link

算是会写回滚莫队了吧

没什么好解释的，直接分析代码。

sort(q + 1, q + 1 + m, [](const Query& x, const Query& y) {
	if (block[x.l] != block[y.l]) return block[x.l] < block[y.l];
	else return x.r < y.r;
});

for (int i = 1, j = 1; j <= (n - 1) / siz + 1; j++) { // 依次遍历每个块
	int pos = Min(j * siz, n);
	l = pos + 1, r = pos, res = 0;
	// 这道题是只增加莫队，所以 左右端点 从空开始扩张
	while (block[q[i].l] == j) { // 左端点在块中的查询
		if (q[i].r <= pos) { // 右端点也在块中直接暴力算
			ans[q[i].ind] = cal(q[i].l, q[i].r);
			i++;
			continue;
		}
		while (r < q[i].r) add(++r); // 扩张
		LL rec = res; // 此时的左端点还在这个块的最右端此处的 res 可以作为历史版本记录使用
		while (l > q[i].l) add(--l); // 扩张
		ans[q[i].ind] = res; // 记录答案
		while (l <= pos) del(l++); // 把左端点拉回这一块的最右端并撤销贡献
		res = rec; // 还原
		i++;
	}
	while (r > pos) del(r--); // 所有清空贡献
}

$\mathbb{Rmq \ Problem}$

link

依然是回滚

这个是只删除的回滚莫队。

sort(q + 1, q + 1 + m, [](const Query& x, const Query& y) {
	if (block[x.l] != block[y.l]) return block[x.l] < block[y.l];
	else return x.r > y.r;
});

for (int i = 1, j = 1; j <= (n - 1) / siz + 1; j++) {
	int pos = Min(j * siz, n);
	l = pos + 1 - siz, r = n, res = cal(l, r);
	// 这个是只删除的回滚莫队
	// 在一开始，把左端点拉到这个块的最左端，右端点拉到 n
	memset(sum, 0, sizeof(sum));
	for (int k = l; k <= r; k++) sum[a[k]]++; // 一开始就要算贡献
	while (block[q[i].l] == j) {
		if (q[i].r <= pos) { // 左右端点都在同一个块里暴力算
			ans[q[i].ind] = cal(q[i].l, q[i].r);
			i++;
			continue;
		}
		while (r > q[i].r) del(r--); // 缩小
		int rec = res; // 此时的左端点在这个块的最左端，答案可以作为历史版本继续算
		while (l < q[i].l) del(l++); // 缩小
		ans[q[i].ind] = res;
		while (l > pos + 1 - siz) add(--l); // 撤销
		res = rec; // 还原
		i++;
	}
	while (r < n) add(++r); // 清空贡献
}

更具体地，回滚莫队工作原理就是如下几步：

• 固定左端点，右端点一直保持单调移动做出贡献
• 记录下此时的贡献作为备份
• 移动左端点回答当前的询问
• 撤销左端点的贡献，并把当前的答案还原成备份

形象一点，就是一个左端点先不动，右端点一直往一个方向动，当右端点碰到询问区间的边界时(*)，记录答案
作为备份并挪动左端点到询问区间的左端点进行回答，然后把左端点拉回固定的位置，一路上撤回贡献，回
到起点时，发现当前的状态和(*)是一致的，那么可以直接把答案还原成备份，继续重复以上操作。

$\mathbb{permu}$

link

线段树乱杀

看到范围小，可以直接普通莫队 + 线段树查询区间最长连续 $1$ 来做，可能要比回滚慢一点，但是能过且好写。