CF1098F 题解
EuphoricStar
·
·
题解
提供一个后缀数组的做法，基本想法来源于 lzyqwq 的 这篇题解。
考虑先对 s 求出后缀数组 sa，排名数组 rk 和 height 数组 h。单组询问的答案即为：
\begin{aligned} & r - l + 1 \\ + & \sum\limits_{k = 1}^{rk_l - 1} [sa_k \in [l, r]] \min(\min\limits_{k < i \le rk_l} h_i, r - sa_k + 1) \\ + & \sum\limits_{k = rk_l + 1}^n [sa_k \in [l, r]] \min(\min\limits_{rk_l < i \le k} h_i, r - sa_k + 1) \end{aligned}
这样本题就被转化成了一个序列问题。
考虑分治，设当前分治区间为 [L, R]，设 mid = \left\lfloor\frac{L + R}{2}\right\rfloor，每次计算 k 和 rk_l 分别在 [L, mid], [mid + 1, R] 或 [mid + 1, R], [L, mid] 的情况。只讨论 k \in [L, mid]，rk_l \in [mid + 1, R] 的情况，另一种是完全对称的。
设 pre_i = \min\limits_{j = i}^{mid} h_j, suf_i = \min\limits_{j = mid + 1}^i h_j。要求：
\sum\limits_{k = L}^{mid} [sa_k \in [l, r]] \min(\min(pre_{k + 1}, suf_{rk_l}), r - sa_k + 1)
直接硬拆 \min 计算不可避免地要三维偏序，不可接受。考虑先把全部 k 的贡献都当作 \min(pre_{k + 1}, suf_{rk_l})，再处理算错的部分。也就是首先我们要求：
\sum\limits_{k = L}^{mid} [sa_k \in [l, r]] \min(pre_{k + 1}, suf_{rk_l})
钦定是 pre_{k + 1} 还是 suf_{rk_l} 取到 \min 后就是二维数点问题。
然后我们处理算错的贡献，要求：
\sum\limits_{k = L}^{mid} [sa_k \in [l, r] \land r - sa_k + 1 \le \min(pre_{k + 1}, suf_{rk_l})] (r - sa_k + 1 - \min(pre_{k + 1}, suf_{rk_l}))
这里相当于要求 sa_k 的范围是 [\max(l, r - \min(pre_{k + 1}, suf_{rk_l}) + 1), r]。
到这里你发现拆 \min 之后又是三维偏序了，不可接受。仍然沿用上面的 trick，先把全部的 \min(pre_{k + 1}, suf_{rk_l}) 都当成 pre_{k + 1}。所求变为：
\sum\limits_{k = L}^{mid} [sa_k \in [l, r] \land r - sa_k + 1 \le pre_{k + 1}] (r - sa_k + 1 - pre_{k + 1})
这是一个二维数点问题。
最后考虑 \min(pre_{k + 1}, suf_{rk_l}) 实际是 suf_{rk_l} 的情况，即求：
\sum\limits_{k = L}^{mid} [sa_k \in [l, r] \land r - sa_k + 1 \le suf_{rk_l} \land pre_{k + 1} \ge suf_{rk_l}] (pre_{k + 1} - suf_{rk_l})
相当于是 sa_k \in [\max(l, r - suf_{rk_l} + 1), r]，仍然是二维数点问题。
这样就做完了。每个位置和每个询问参与到了 \log 个二维数点，设 n, q 同阶，总时间复杂度为 O(n \log^2 n)。
code