题解 P7721 [Ynoi2007] rvrewsus

critnos · 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 实现快速乘就还好。