同求
by Fractured_Angel @ 2024-05-03 22:46:30
@[sansesantongshun](/user/866613) 可以。（需要基数排序）。把操作离线，可以一个块一个块得考虑贡献。首先修改操作很容易，用归并就是不带log的。我们考虑一次修改操作对于一个块只有三种情况，没修改到，整块修改，块的一部分修改了。
我们考虑每一个块对所有询问的贡献，把q次操作按照对这个块的第三类修改分隔开，对于分开的每一段里，按照询问的实际大小对询问操作进行基数排序（说实际大小是因为如果对块有整体修改，询问的大小就要减去整体加的东西）这样再对排好序的块进行查询，单段q就是根号n的复杂度。
而最多会分多少段呢。q段。所以复杂度是qsqrtn
by 聊机 @ 2024-05-04 10:28:15
@[聊机](/user/290959) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
by sansesantongshun @ 2024-05-04 11:53:57
啊？$O(n\sqrt n)$ 过 $10^6$ 有点奇幻了吧（跪
这个常数大概是我这个傻逼羡慕不来的%%%
by _venti @ 2024-05-06 21:09:27
@[_venti](/user/1033727) 脑抽打错了 $m\sqrt{n}$
by sansesantongshun @ 2024-05-11 20:51:42
@[_venti](/user/1033727) 这么说你这个是 $n\sqrt{n}\log(n)$ 的，这道题 $n,m$ 不同数量级
by sansesantongshun @ 2024-05-11 20:54:02
@[sansesantongshun](/user/866613) 那没事了（叹
by _venti @ 2024-05-11 21:19:19
@[聊机](/user/290959) 感谢，已经实现了
by sansesantongshun @ 2024-05-11 23:17:26
@[sansesantongshun](/user/866613) 强！
by 聊机 @ 2024-05-12 14:13:25
分散层叠可以 $O(n\sqrt n)$
by fresh_boy @ 2024-05-14 14:53:18