P9016 [USACO23JAN] Find and Replace G 题解

OMG_wc · 2023-02-06 16:43:02 · 题解

从后往前考虑每次替换，同时用 26 棵二叉树，来维护当前每个字符 c 最终形成的字符串。

在建树的时候，同样的子树不用再复制一份，而是直接建边，这样虽然总点数可能高达 2^{114514} 次，实际建的边却只是 O(\sum|s|) 条。

具体来说，当前考虑的是第 [k,n] 轮替换后的结果，第 k 轮替换规则为 c_k \rightarrow s_k。对字符串 s_k 的每个字符在 [k+1,n] 轮替换后的结果按从左到右的顺序两两合并，然后合并后的二叉树作为字符 c_k 当前的结果。合并时保证所有非叶结点都有两个孩子，最终字符都存在于叶结点上。

结点信息要维护树的大小，为防止溢出不要超过 10^{18}。

因为是二叉树，可以像线段树这样查询：途径的结点中是 [l,r] 内部的点有 O(r-l) 个，其他包含一部分的途径点只在每层的两端出现，这样每层只有常数个这样的点，而树高是 O(n) 的，所以总的途经点是 O(n+r-l) 级别的。

总时间复杂度 O(r-l+\sum|s|)，代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF = 1e18;
const int N = 200105;

struct Node {
    char v;
    int lc, rc;
    LL sz;
} tr[N];
int root[26], ck;
char c[N];
string s[N];
void query(int u, LL l, LL r) {
    if (r <= 0 || l > tr[u].sz) return;
    if (tr[u].v == '#') {
        query(tr[u].lc, l, r);
        query(tr[u].rc, l - tr[tr[u].lc].sz, r - tr[tr[u].lc].sz);
    } else {
        putchar(tr[u].v);
    }
}
int main() {
    LL l, r, n;
    cin >> l >> r >> n;
    for (int i = 1; i <= n; i++) cin >> c[i] >> s[i];
    for (int i = 0; i < 26; i++) {
        tr[++ck] = {char('a' + i), 0, 0, 1};
        root[i] = ck;
    }
    for (int i = n; i >= 1; i--) {
        int now = 0;
        for (auto x : s[i]) {
            x -= 'a';
            if (now == 0)
                now = root[x];
            else {
                tr[++ck] = {'#', now, root[x], min(INF, tr[now].sz + tr[root[x]].sz)};
                now = ck;
            }
        }
        root[c[i] - 'a'] = now;
    }
    query(root[0], l, r);
    putchar('\n');
    return 0;
}