P8796 线段树

Usada_Pekora · 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;
}