如你所见，我代码调出来了。（喜）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
定义可替换字符串如下：
对于 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 的高分。
而且正解也很简单了……吗？
接下来才是真正折磨的点。
首先前面两个要求可以通过哈希快速寻找，后面的要求字典树很可做。
所以考虑 map 套 Trie 套 Trie。
map 第一个值是字符串的哈希值，第二个值是第一个 Trie 的根，可以用来快速查找满足前面两个条件的 Ai,BiA_i,B_iAi ,Bi 。
然后遍历 [Si,...,Sl][S_i,...,S_l][Si ,...,Sl ]，如果有这个节点，就再暴力进入第二个 Trie 找 [Sr,...,Sj][S_r,...,S_j][Sr ,...,Sj ]，将答案加上存在的个数。
例如：
构建 Trie 如下（黑节点表示 Trie 根，红节点表示前缀 Trie，绿节点表示后缀 Trie，标在绿节点上的黑字表示出现该字符串的个数）：
然后查询首先通过哈希找到根，然后按照建树相同的方法查询即可。蓝色的为遍历过程。
答案就为所有节点上的权值之和 1+0+1=21+0+1=21+0+1=2。
我们分析一下时间复杂度：
乍一看，很暴力，对于每个红节点都得搜一下叶子结点，最坏情况可能一次查询就要搜完整棵树。
但是——我们仔细分析一下建树过程。
注意到一个绿色节点就对应至少一个字符。
如果出题人想卡我们的话，肯定得像以下方法构造：
造出来的这颗树大致长这样：
第一个 Trie 与第二个 Trie 深度均为 O(L)O(\sqrt L)O(L )。
而查询，如果要卡满，就需要把前后缀都拉满，字符串长度也得达到 O(L)O(\sqrt L)O(L )。
所以这时虽然单次查询复杂度为 O(L)O(L)O(L)，但总共也只会出现 O(L)O(\sqrt L)O(L ) 次查询，时间复杂度为 O(LL)O(L\sqrt L)O(LL )。
但这个复杂度要是实现得劣一点就寄了，所以我们还得减小时间复杂度。
注意到第二个 Trie 上的节点就对应了 O(size)O(size)O(size) 个字符串，所以我们可以预处理出这些字符串的答案，然后查询时直接哈希二分找到对应的答案即可。
这样的话每次查询先 O(∣Si∣)O(|S_i|)O(∣Si ∣) 遍历第一个 Trie，然后 O(log2n)O(\log^2 n)O(log2n) 二分判断第二个 Trie 包含的最长的前缀，时间复杂度就被我们优化到了 O(Llog2L)O(L\log^2 L)O(Llog2L)。
这时有人就要问了：这 L=5×106L=5\times 10^6L=5×106，Llog2L≈2.5×109L\log^2 L\approx 2.5\times 10^9Llog2L≈2.5×109，你这跟没优化有什么区别？
我们看看出题人最多能把我们卡成什么样。
首先看 LLL 的定义：∑∣Si∣+∣Ti∣\sum |S_i|+|T_i|∑∣Si ∣+∣Ti ∣。所以我们得把 LLL 除以 222 计算。1.2×1091.2\times 10^91.2×109。
然后经过一番思考，发现最强的数据也就是按照上面的构造方法，将深度构造成 O(L)O(\sqrt L)O(L )。所以两个二分的大小其实都是 O(logL)O(\log \sqrt L)O(logL ) 的，又得乘一个 14\frac{1}{4}41 。3×1083\times 10^83×108。而且你再怎么乱搞二分的常数都为 111 吧。
这样，我们就通过了该题。
