在家想了一整天+在学校想了一整天才想出来。
题意解析：
定义可替换字符串如下：
对于 A,B,S,T(∣A∣=∣B∣,∣S∣=∣T∣,A≠B,S≠T)A,B,S,T(|A|=|B|,|S|=|T|,A\not= B,S\not= T)A,B,S,T(∣A∣=∣B∣,∣S∣=∣T∣,A=B,S=T)，
若存在至少一个 [l,r][l,r][l,r] 使得 [Sl,...,Sr]=A[S_l,...,S_r]=A[Sl ,...,Sr ]=A，且将其中一个 [Sl,...,Sr][S_l,...,S_r][Sl ,...,Sr ] 替换为 BBB 后 S=TS=TS=T，
则成 A,BA,BA,B 为 S,TS,TS,T 的可替换字符串。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
给定 nnn 个字符串组合 [A1,B1],[A2,B2],...,[An,Bn][A_1,B_1],[A_2,B_2],...,[A_n,B_n][A1 ,B1 ],[A2 ,B2 ],...,[An ,Bn ]，其中 ∣Ai∣=∣Bi∣|A_i|=|B_i|∣Ai ∣=∣Bi ∣。给出 qqq 次询问，每次询问给出两个字符串 Si,TiS_i,T_iSi ,Ti ，求出满足 Ai,BiA_i,B_iAi ,Bi 为 Si,TiS_i,T_iSi ,Ti 的可替换字符串的 iii 的个数，特别地，若 ∣Si∣≠∣Ti∣|S_i|\not= |T_i|∣Si ∣=∣Ti ∣，输出 0。
1≤n,q≤2×105,1≤∑∣Ai∣+∣Bi∣,∑∣Si∣+∣Ti∣≤5×1061\le n,q\le 2\times 10^5,1\le \sum |A_i|+|B_i|,\sum |S_i|+|T_i|\le 5\times 10^61≤n,q≤2×105,1≤∑∣Ai ∣+∣Bi ∣,∑∣Si ∣+∣Ti ∣≤5×106。即 ∑Ai≤2.5×106\sum A_i\le 2.5\times 10^6∑Ai ≤2.5×106，且对于所有答案不为 000 的询问，∑Si≤2.5×106\sum S_i\le 2.5\times 10^6∑Si ≤2.5×106。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
首先考虑如何才能满足 A,BA,BA,B 为 S,TS,TS,T 的可替换字符串。
定义两个字符串 S,T(∣S∣=∣T∣,S≠T)S,T(|S|=|T|,S\not= T)S,T(∣S∣=∣T∣,S=T) 的核心为在所有满足除去该区间以外，所有的 Si=TiS_i=T_iSi =Ti 的区间中，长度最短的一个。
令 [l,r][l,r][l,r] 为 S,TS,TS,T 的核心，[l′,r′][l',r'][l′,r′] 为 BBB 的核心，A,BA,BA,B 为 S,TS,TS,T 的可替换字符串当且仅当：
* [Sl,...,Sr]=[Al′,...,Ar′][S_l,...,S_r]=[A_{l'},...,A_{r'}][Sl ,...,Sr ]=[Al′ ,...,Ar′ ]。
* [Tl,...,Tr]=[Bl′,...,Br′][T_l,...,T_r]=[B_{l'},...,B_{r'}][Tl ,...,Tr ]=[Bl′ ,...,Br′ ]。
* [...,Al′][...,A_{l'}][...,Al′ ] 为 [...,Sl−1][...,S_{l-1}][...,Sl−1 ] 的后缀。
* [Ar+1,...][A_{r+1},...][Ar+1 ,...] 为 [Sr+1,...][S_{r+1},...][Sr+1 ,...] 的前缀。
知道这个结论后，就可以通过哈希 O(nq)O(nq)O(nq) 求出了，搭配性质 B 可以得到 70pts70pts70pts 的高分。
而且正解也很简单了……吗？
接下来才是真正折磨的点。
首先前面两个要求可以通过哈希快速寻找，后面的要求字典树很可做。
所以考虑 umap 套 Trie 套 Trie。
umap 第一个值是字符串的哈希值，第二个值是第一个 Trie 的根，可以用来快速查找满足前面两个条件的 Ai,BiA_i,B_iAi ,Bi 。
两个 Trie 分别存储 [...,Ai,l][...,A_{i,l}][...,Ai,l ] 与 [Ai,r,...][A_{i,r},...][Ai,r ,...]，其中第一个倒序存储。
这样预处理显然可以做到 O(∑∣Ai∣)O(\sum |A_i|)O(∑∣Ai ∣)。
然后考虑查询怎么做。
我们先求出核心的哈希值，在 umap 里找。
然后遍历 [Si,...,Sl][S_i,...,S_l][Si ,...,Sl ]，如果有这个节点，就再暴力进入第二个 Trie 找 [Sr,...,Sj][S_r,...,S_j][Sr ,...,Sj ]，将答案加上存在的个数。
这样时间复杂度是多少？
首先看单次询问。
前面遍历 [Si,...,Sl][S_i,...,S_l][Si ,...,Sl ] 是 O(∣S∣)O(|S|)O(∣S∣) 的，后面遍历 [Sr,...,Sj][S_r,...,S_j][Sr ,...,Sj ] 也是 O(∣S∣)O(|S|)O(∣S∣) 的，所以看似是 O(∣S∣2)O(|S|^2)O(∣S∣2) 的，但是注意到我们总共的节点最多有 O(∑∣Ai∣)O(\sum |A_i|)O(∑∣Ai ∣) 个，所以时间复杂度应为 O(min{∣S∣2,∑∣Ai∣}O(\min\{|S|^2,\sum |A_i|\}O(min{∣S∣2,∑∣Ai ∣})。
这样可以证明整体最坏复杂度为 O(∑∣Si∣∑∣Si∣)O(\sum |S_i|\sqrt{\sum |S_i|})O(∑∣Si ∣∑∣Si ∣ )。
但写完后发现似乎毛用没有，还不如 O(nq)O(nq)O(nq) 做法。
怎么办呢？
我们发现第二个 Trie 需要沿着根一个一个找，太浪费了。
我们可以预处理完第二个 Trie 时搜一下整棵树，预处理查询的字符串若为 [Sr,...,Sj][S_r,...,S_j][Sr ,...,Sj ] 的前缀和。然后丢掉第二个 Trie，换成所有可能字符串的哈希值。显然这个大小和第二个 Trie 的大小一样。
这样查询的时候我们只需要二分出最长的存在的前缀，然后直接查询即可。
这样子时间复杂度就是 O(∑∣Si∣log∑∣Si∣log∑∣Ai∣)=O(Llog2L)O(\sum |S_i|\log \sum |S_i|\log \sum |A_i|)=O(L\log^2 L)O(∑∣Si ∣log∑∣Si ∣log∑∣Ai ∣)=O(Llog2L)，并且卡不满，而且瓶颈在于小常数的二分，不要用 map，正常写就行。
