自动搬运

查看原文

来自洛谷，原作者为

	critnos 咔菲好喝。

搬运于2025-08-24 22:32:28，当前版本为作者最后更新于2022-10-01 13:08:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

也许是一血，吗？

其实不是特别难。。

考虑 $a_i$ 互不相同的作法。除了莫队二次离线，更强的做法是用 [Ynoi2013] D2T2 的分治方法。

就是对值域分块，这样每块的信息是容易合并的。对于每块只有 $O(n)$ 个答案。考虑在每块的值域上分治。合并值域 $[l,mid]$ 和 $[mid+1,r]$，可以直接 $O(n^2)$ 合并。这样时间复杂度是 $T(n)=O(n^2)+2T(n/2)$，$T(n)=O(n^2)$。

对每块 $O(1)$ 查询询问区间对应的答案就可以做到 $O(n\sqrt n)$。

考虑会重复的情况。可以发现上面的分治仍然适用，只要让每块内的元素个数 $O(\sqrt n)$。对于重复的数字在内部预处理就可以。一个问题是现在的值域数组不均匀了。一个简单的处理手法是，对序列带权划分，将序列分为 $[l,p),[p,p],(p,r]$ 三部分，满足 $[l,p),(p,r]$ 都不超过 $[l,r]$ 的一半。这样最后合并两次，时间复杂度仍然是 $T(n)=O(n^2)+2T(n/2)$。

另一个问题是一个数出现次数如果超过 $\sqrt n$ 是没法分块的。但是这种数出现次数 $O(\sqrt n)$ 直接特殊处理就行。。

所以这个问题已经解决了。对于值域的整块，用上面的方法处理；对于值域的散块，在序列上跑个莫队就行。

时间复杂度 $O(n\sqrt n)$。

卡常方面用 long double 实现快速乘就还好。