到底是谁在想出那些巨大困难的做法

· · 题解

我声称这个题就是 CSP-S T3。

首先难点是跨过 L 两边，也即 l \in [1, L - 1], r \in [L, R] 的贡献。

对于每一个串 s_i，枚举分割点 p，产生贡献当且仅当 s_i[1, p - 1] 是 t[1, L - 1] 的后缀，且 s_i[p, \lvert s_i \rvert] 是 t[L, R] 的前缀。

我们利用「fail 树上 a 串对应点是 b 串对应点的祖先」来刻画 「a 串是 b 串的后缀」的限制。

把所有 s 的正反串建出两个 ACAM，在 s_i[1, p - 1] 的正串和 s_i[p, \lvert s_i \rvert] 的反串上打一个标记 (i, p)。

查询时只需求出 t[1, L - 1] 的正串和 t[L, R] 的反串二者到根的链上，标记集合的交集大小，这是一个简单的二维数点问题，离线 BIT 即可。注意后者需要用一个倍增来处理 \le R 的限制。

于是以 O(S \lvert \Sigma \rvert + (m + S) \log S + \lvert t \rvert) 的时间复杂度解决了这个题。

Submission。

我的 CSP-S T3 写了一模一样的做法，但是那个 S 是 5 \times 10^6 于是我获得了高达 80 分（