本题是否有nsqrtn算法

sansesantongshun @ 2024-05-03 22:17:39

by Fractured_Angel @ 2024-05-03 22:46:30

同求

by 聊机 @ 2024-05-04 10:28:15

@sansesantongshun 可以。（需要基数排序）。把操作离线，可以一个块一个块得考虑贡献。首先修改操作很容易，用归并就是不带log的。我们考虑一次修改操作对于一个块只有三种情况，没修改到，整块修改，块的一部分修改了。

我们考虑每一个块对所有询问的贡献，把q次操作按照对这个块的第三类修改分隔开，对于分开的每一段里，按照询问的实际大小对询问操作进行基数排序（说实际大小是因为如果对块有整体修改，询问的大小就要减去整体加的东西）这样再对排好序的块进行查询，单段q就是根号n的复杂度。

而最多会分多少段呢。q段。所以复杂度是qsqrtn

by sansesantongshun @ 2024-05-04 11:53:57

@聊机 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

by toolazy @ 2024-05-06 21:09:27

啊？O(n\sqrt n) 过 10^6 有点奇幻了吧（跪

这个常数大概是我这个傻逼羡慕不来的%%%

by sansesantongshun @ 2024-05-11 20:51:42

@_venti 脑抽打错了 m\sqrt{n}

by sansesantongshun @ 2024-05-11 20:54:02

@_venti 这么说你这个是 n\sqrt{n}\log(n) 的，这道题 n,m 不同数量级

by toolazy @ 2024-05-11 21:19:19

@sansesantongshun 那没事了（叹

by sansesantongshun @ 2024-05-11 23:17:26

@聊机 感谢，已经实现了

by 聊机 @ 2024-05-12 14:13:25

@sansesantongshun 强！

by fresh_boy @ 2024-05-14 14:53:18

分散层叠可以 O(n\sqrt n)