P8796 [蓝桥杯 2022 国 AC] 替换字符

Genshineer · 2023-11-24 21:42:04 · 题解

P8796 [蓝桥杯 2022 国 AC] 替换字符

考虑一个经典问题：

每次给定区间 [l,r] 和 x,y，要求把区间内的所有 x 改为 y。

先考虑没有给定 l,r 即每次作用于整个序列怎么做。

不难想到，可以对着值域开一个链表，每次区间修改相当于把接在 x 后的所有元素全部接在 y 后面。时间复杂度 O(1)，非常理想。所以对于整个块的修改是好做的。

既然对整个块是好做的，那么就很容易想到分块了。

每个块内分别存储 \Sigma 个链表，每个链表存当前字符对应哪些位置，整块的修改就解决了。对于散块修改显然可以直接暴力扫过要修改的字符 x 对应的链表查询是否存在当前位置，如果存在对于对应位置直接修改就可以了。查找最坏为 O(\sqrt{n})，修改为 O(1)，可以通过本题。

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

const int maxn = 1e5 + 5, sqrm = 1e3;
int tot, t, n, m, pos[maxn];
struct lnk {
    int nxt, id;
} e[maxn << 1];
string s, ans;

struct data {
    int hd[30], l, r;

    inline void insert(int id, char c) {
        int u = c - 'a';
        e[++tot].nxt = this->hd[u];
        e[tot].id = id;
        this->hd[u] = tot;
    }

    inline void re(char a, char b) {
        int u = a - 'a', v = b - 'a';
        if (!this->hd[u])
            return;
        int i = this->hd[u];
        while (e[i].nxt)
            i = e[i].nxt;
        e[i].nxt = this->hd[v];
        this->hd[v] = this->hd[u];
        this->hd[u] = 0;
    }

    inline void change(int id, char x, char y) {
        int i = this->hd[x - 'a'], j = this->hd[x - 'a'];
        while (e[i].id != id and e[i].nxt)
            i = e[i].nxt;
        while (e[e[j].nxt].id != id and e[j].nxt)
            j = e[j].nxt;
        if (i == this->hd[x - 'a']) {
            this->hd[x - 'a'] = e[i].nxt;
            e[i].nxt = this->hd[y - 'a'];
            this->hd[y - 'a'] = i;
            return;
        }
        e[j].nxt = e[i].nxt;
        e[i].nxt = this->hd[y - 'a'];
        this->hd[y - 'a'] = i;
    }

    inline bool check(int id, char c) {
        int u = c - 'a';
        for (int p = this->hd[u]; p; p = e[p].nxt)
            if (e[p].id == id)
                return 1;
        return 0;
    }
} b[sqrm];

inline void build() {
    t = sqrt(n);
    for (int i = 1; i <= t; i++) {
        b[i].l = b[i - 1].r + 1;
        b[i].r = b[i].l + t - 1;
    }
    b[t].r = n;
    for (int i = 1; i <= t; i++) {
        for (int j = b[i].l; j <= b[i].r; j++) {
            pos[j] = i;
            b[i].insert(j, s[j]);
        }
    }
}

inline void modify(int l, int r, char x, char y) {
    int p = pos[l], q = pos[r];
    if (p == q) {
        for (int i = l; i <= r; i++)
            if (b[p].check(i, x))
                b[p].change(i, x, y);
    }
    else {
        for (int i = l; i <= b[p].r; i++)
            if (b[p].check(i, x))
                b[p].change(i, x, y);
        for (int i = p + 1; i < q; i++)
            b[i].re(x, y);
        for (int i = b[q].l; i <= r; i++)
            if (b[q].check(i, x))
                b[q].change(i, x, y);
    }
}

inline void getans() {
    for (int i = 1; i <= n; i++)
        ans += " ";
    for (int i = 1; i <= t; i++)
        for (int j = 0; j < 26; j++)
            for (int p = b[i].hd[j]; p; p = e[p].nxt)
                ans[e[p].id - 1] = j + 'a';
} 

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    string tmp;
    cin >> tmp;
    s = " ";
    for (int i = 1; i <= (int)tmp.size(); i++)
        s += tmp[i - 1];
    n = s.size() - 1;
    cin >> m;
    build();
    for (int i = 1; i <= m; i++) {
        int l, r;
        char x, y;
        cin >> l >> r >> x >> y;
        modify(l, r, x, y);
    }

    getans();

    cout << ans;
}