T1 Find and Replace G

个人思路：
从后往前做，每次修改，替换前一个修改里面的字母，显然是错的，因为没替换更前面的字母。

然后就想不出来了。

正解：
第 \(i\) 次修改 \(c,s\)，相当于 \(c\) 被替换成 \(s\) 中每个字母在 \([i + 1,n]\) 次操作后对应的字符串之和。

于是我们从后往前做，对于每个字母建一个二叉树用来计算每个字母变成的字符串。

具体而言，我们先建立一些节点表示 字母 \(\text{a~z}\)，然后对于每个字母建立一个指针，表示这个字母被替换为指向节点的子树内所有字母，显然，在没有修改时，每个字母指向它本身对应的节点。

从后往前做，每次修改 \(c,s\)，从左到右遍历 \(s\) 中每一个字母：

1.对于前两个字母，新建一个节点，两个儿子指向这两个字母的指针指向的节点。
2.对于剩余字母，每个字母新建一个节点，左儿子指向上一个新建节点，右儿子指向当前字母。
每个节点记录一下子树内的字母数，以供查询。

遍历完成后，\(c\) 的指针指向新建的节点。

因为对于一个字符串 \(s\)，新建节点数 \(= |s|-1\)，所以总共新建节点数 \(< |s| \le 2 \times 10^5\)。

查询时，我们从 \(\text{a}\) 指向的节点开始查询。

当我们遍历到一个节点时，其左儿子子树内的字母数为 \(cnt\)：

1.\(cnt \ge r\)，查询左儿子 \([l,r]\)。
2.\(cnt \le l\)，查询右儿子 \([l-cnt,r-cnt]\)。
3.否则先查询左儿子 \([l,cnt]\)，再查询右儿子 \([1,r-cnt]\)。