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)$ 。