10.26 模拟赛 C

C 秋天的第一杯奶茶

以下复杂度默认 $n,m,q$ 同阶。

考虑询问 $[x,y]$ ,差分一下就是区间 $[1,x-1]$ 的修改对 $[x,y]$ 的询问的影响(记作 $[1,x-1][x,y]$)。

然后可以直接莫队一下,这个往左往右加入拿 BIT 维护即可。复杂度 $O(n\sqrt n \log n)$ ,期望得分 $85\sim 95$ 、

这种东西的优化很类似于区间逆序对。考虑再次差分,变成 $[1,x - 1][1,y] - [1,x - 1][1,x - 1]$ ,也就是进行完 $[1,x-1]$ 的操作后询问 $[1,y] - [1,x-1]$ 。

首先 $[1,x][1,x]$ 是很可做的, 考虑向后添加一个东西,如果是询问那么在修改的 BIT 上查,否则在询问的 BIT 上查,并且改一下 BIT ,于是 $O(n\log n)$ 即可预处理。

然后考虑 $[1,x][1,y]$ 怎么处理,首先可以莫队,复杂度 $O(n\sqrt n \log n)$ 。

然后考虑二次离线,把修改挂在 $x$ 上。然后 $x$ 会移动 $O(n)$ 次,$y$ 会移动 $O(n\sqrt n)$ 次。但是 $x$ 的修改是区间加,可以用类似区间加 BIT 的操作把区间修改变成单点修改。

用一个根号平衡可以做到 $O(n\sqrt n)$ 。

文章作者: yijan
文章链接: https://yijan.co/2020/11/08/1026-mo-ni-sai-c/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog