Description
Link：gym103483 C
给出一个包含 n 个字符串的集合 D 以及一个字符串 s，你需要找出集合 D 中字典序小于 s 的字符串数量。
字符串 s 会经过 Q 次修改，每次修改会给出一个整数 k 以及一个字符 c，表示将字符串 s 从第 k 个字符开始到字符串末尾的所有字符替换成 c。每次修改完字符串 s 之后，你都需要求出集合 D 中字典序小于 s 的字符串数量。
数据范围：1≤n,Q≤106，1≤∣s∣≤106，字符串集合 D 的总长不超过 106。
时空限制：2s / 512MiB。
Solution
考虑建出 Trie 树，设 cnt[u] 表示节点 u 上的终止节点个数，设 sze[u] 表示节点 u 的子树内的终止节点个数。
设 go(u,c) 表示节点 u 往节点 δ(u,c) 走产生的贡献，则 go(u,c)=cnt[u]+∑i<csze[δ(u,i)]。
考虑把贡献记在点上，即 value(δ(u,c))=go(u,c)，则一个字符串 s 对应的答案即为其在 Trie 树上经过的节点的贡献之和（叶子需要特殊考虑）。
于是我们只需维护字符串 s 在 Trie 树上的位置即可。维护 end(u,c) 表示节点 u 一直沿着字符 c 走到达的节点。使用 end 数组向下走，再使用树上倍增向上走。特别处理一下叶子节点的贡献（即字符串 s 走出了 Trie 树）即可。
MENASQ_TGRM 大佬的优秀做法：在 end(u,c) 中约束向下走到达的节点深度，深度 ≤n 即可。