P10149 [Ynoi1999] XM66F 题解
vegetaBle_king
·
·
题解
可能更好的阅读体验
考虑值域从小往大扫，同时维护另一个序列 b，扫过的地方 b 对应的位置改成 1，那么一对位置 (i, k) \ (a_i = a_k) 的贡献是 b_{i \sim k} 的和。
显然每种 a_i 对应的位置对 (i, k) 贡献是独立的，那么我们只考虑一种。假设这种数 x 的出现次数为 C，出现位置分别为 p_{1 \sim C}，设 b_{p_i \sim p_{i + 1}} 的和为 c_i。
我们有两种方法统计这种贡献：
- 暴力拆出 C^2 个位置对，变为二维偏序。它的优点在于可以和其他贡献一起跑。
-
设置阈值 B，C \le B 时用第一种方法，C > B 时用第二种方法。后者的总时间复杂度显然是 O(\frac nB(n + q))，前者可以平衡一下做到 O(nB + q\sqrt n)。解出 B = \sqrt n 时总时间复杂度为 O((n + q)\sqrt n)。因为要扫描线所以不支持强制在线，被莫队做法打爆了。