自动搬运

查看原文

来自洛谷，原作者为

	Usada_Pekora 兎田ぺこら/大傻Peko_Official/AFO

搬运于2025-08-24 22:42:33，当前版本为作者最后更新于2022-11-24 16:05:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

注意到值域很小，直接对值域冲。

我们只需要维护，对于每个区间，每个字符被覆盖成了哪个别的字符即可，这个可以线段树解决。

具体地，对于每个节点维护一个长度 $26$ 的 lazytag 表示对于这个区间，每个字母分别被替换成了哪个字母，直接暴力下传即可。

标记下推大概是这样：

for (int i = 0; i < 26; i++)
	lzy[ls][i] = lzy[p][lzy[ls][i]];
for (int i = 0; i < 26; i++)
	lzy[rs][i] = lzy[p][lzy[rs][i]];
for (int i = 0; i < 26; i++)
	lzy[p][i] = i;

复杂度 $O(m|\Sigma|\log n)$，其中 $|\Sigma|$ 是字符集大小 $26$。

然后就差不多结束了，具体可以看代码实现。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, K = 26;
int lzy[N * 2][K], ls[N * 2], rs[N * 2], val[N * 2], idx, n, m;
char a[N];
inline int build(int l, int r) {
	int p = ++idx;
	for (int i = 0; i < K; i++)
		lzy[p][i] = i;
	if (l == r) {
		val[p] = a[l] - 'a';
		return p;
	}
	int mid = (l + r) >> 1;
	ls[p] = build(l, mid);
	rs[p] = build(mid + 1, r);
	return p;
}
inline void pushdown(int p) {
	for (int i = 0; i < K; i++)
		lzy[ls[p]][i] = lzy[p][lzy[ls[p]][i]];
	for (int i = 0; i < K; i++)
		lzy[rs[p]][i] = lzy[p][lzy[rs[p]][i]];
	for (int i = 0; i < K; i++)
		lzy[p][i] = i;
}
inline void modify(int p, int l, int r, int L, int R, int x, int y) {
	if (L <= l && r <= R) {
		for (int i = 0; i < K; i++)
			if (lzy[p][i] == x)
				lzy[p][i] = y;
		return;
	}
	pushdown(p);
	int mid = (l + r) >> 1;
	if (L <= mid)
		modify(ls[p], l, mid, L, R, x, y);
	if (R > mid)
		modify(rs[p], mid + 1, r, L, R, x, y);
}
inline void print(int p, int l, int r) {
	if (l == r) {
		printf("%c", lzy[p][val[p]] + 'a');
		return;
	}
	pushdown(p);
	int mid = (l + r) >> 1;
	print(ls[p], l, mid), print(rs[p], mid + 1, r);
}
signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	cin >> a + 1;
	n = strlen(a + 1);
	build(1, n);
	cin >> m;
	for (int i = 1; i <= m; i++) {
		int l, r;
		char x, y;
		cin >> l >> r >> x >> y;
		x = x - 'a', y = y - 'a';
		modify(1, 1, n, l, r, x, y);
	}
	print(1, 1, n);
	return 0;
}