自动搬运

查看原文

来自洛谷，原作者为

	OMG_wc 幻想家协会会长

搬运于2025-08-24 22:44:36，当前版本为作者最后更新于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;
}