牛客多校第二场 F 题题解

F NIO with String Game

F 题题意：给定 $nn$ 个串 $\{T_n\}\backslash \{T\_n\backslash \}$ 和一个串 $SS$，有以下四种操作：

1. 给 $T_{x}T\_x$ 的末尾增加一个字符；
2. 给 $SS$ 串末尾删除 $pp$ 个字符；
3. 给 $SS$ 串末尾插入 $kk$ 个字符；
4. 查询 $\{T_n\}\backslash \{T\_n\backslash \}$ 中有多少个字符串字典序严格小于 $SS$。

$qq$ 次操作，$n,q\le 5\times 10^{5}n,q\; \backslash leq\; 5\backslash times\; 10^5$，字符串总长小于等于 $2\times 10^{5}2\backslash times\; 10^5$。 解法：根据 $\{T_n\}\backslash \{T\_n\backslash \}$ 离线建立 Trie，加入最终情况的 $\{T_n\}\backslash \{T\_n\backslash \}$，然后将 Trie 树欧拉序化，上建立 BIT，只在 $TT$ 串末尾对应节点标 $11$ 表示一次出现。但是初始情况下打上末尾标记的是初始的 $\{T_n\}\backslash \{T\_n\backslash \}$，随着不断加入字符会将这一标记不断移动。

维护一个栈来记录 $SS$，相同字符压缩存储。同时 Trie 上进行树上倍增，记录从当前节点开始沿 $chch$ 字符走 $2^{k}2^k$ 次所能到的节点。查询操作的时候，对于严格小的串，其欧拉序一定严格在当前节点前面。对于恰好在当前节点的，比较栈中长度和 Trie 树上节点对应的 $TT$ 串长度，相同就不计入。

一些细节：如果当前节点无对应字符出边，则倍增的时候就认为它沿这一字符出边还是走到它自己。此时为了统计 $SS$ 真实情况下已经失配但是还在 Trie 树上的情况，记录一个 $SS$ 串真实长度，对于子树下小于当前 $SS$ 的失配字符 $chch$ 的字符出边，统计下对应的子树大小。

总复杂度 $\mathcal{O}(n+q)\log n\backslash mathcal\; O(n+q)\; \backslash log\; n$。