把所有串正着插入一个 trie $t1$ 中,再倒着插入另一个 trie $t2$ 中.

这样我们查询时将 $s1$ 顺序在 $t1$ 上跑, $s2$ 倒序在 $t2$ 上跑.

问题转换为在 $t1$ 的一个子树和 $t2$ 的一个子树中有多少共同元素.

将每个串在 $t1$ 上 dfs 序位置当做横坐标, 在 $t2$上 dfs 序位置当做纵坐标, 查询时查询矩形.

这是个二维数点, 强制在线, 直接用树套树即可, 我写的二维树状数组.

记录

虚假的强制在线.jpg

发现一种问询只有 26 种可能的真实问询，把这 $26M$ 个问询全部离线下来跑一遍二维数点，再在线走一遍问询，根据算出的答案决定当前问询要回答哪一个答案。

这样 $N$ 大一点也能做！