动态区间第 K 小可以用带修莫队+值域分块吗

diqiuyi @ 2023-04-16 22:27:03

by awdec @ 2023-04-16 22:39:51

区间修 or 单点修？

by ColinKIA @ 2023-04-16 22:42:22

如果是单点修就可以，但是 O(n^ \frac{7}{3})

by World_Creater @ 2023-04-16 22:47:06

@ColinKIA 不是 \dfrac{5}{3} 吗。

by Fatal_Cactus @ 2023-04-16 22:52:40

可以但是复杂度较于树套树过劣。

by E1_de5truct0r @ 2023-04-16 22:57:35

显然可以。

by ColinKIA @ 2023-04-16 23:00:00

@World_Creater 不对，但好像我也错了，你值域分块一次不是 O( \sqrt n) 的吗？

那带修莫队的每次偏移操作时间复杂度不就是 O( \sqrt n)吗？乘上原本带修莫队的 O(n^ \frac{5}{3}) 为 O(n^\frac{13}{6})

by AC_Automation @ 2023-04-16 23:03:41

@ColinKIA 值域分块复杂度是 O(1) 改，O(\sqrt{n}) 查

by AC_Automation @ 2023-04-16 23:05:17

不过单点改为啥不整体二分呢。

by ppip @ 2023-04-16 23:58:11

事实上有 O(n\sqrt n) 的离线线性空间解法。

by World_Creater @ 2023-04-17 00:41:59

@ColinKIA 这个东西不能这么算的，这种值域分块修改 O(1)，查询根号，实际复杂度 O(n^\frac{5}{3}+m\sqrt{n})

不然为什么不用别的数据结构 （树状数组）而是写这么奇怪的东西结果跑出来不如 n^2。

莫队中的值域分块恰好出现了根号平衡的作用（莫队可以看成修改多查询少，而值域分块修改快查询慢）