@[野生林登万](/user/369942) 这两题完全不一样呀。
SDOI 那题完全不需要莫队，用各种 polylog 的数据结构维护就好了；这题是带修莫队最早的例题，目前没有 $\mathrm{polylog}(n)$ 的做法。
by _bzy @ 2023-09-05 12:02:26
@[_bzy](/user/213388) 为啥没有 polylog 啊 /yiw
by 251Sec @ 2023-09-05 12:51:53
@[_bzy](/user/213388) 这题用 Ynoi 镜中的昆虫的 CDQ 不就行了吗，是 $O(n \log^2 n)$ 的
by _ChiFAN_ @ 2023-09-05 13:05:10
@[_ChiFAN_](/user/520748) 不懂欸，要不你发一篇题解，咱好像没看到题解区有 polylog 的。
by _bzy @ 2023-09-05 13:53:07
@[_bzy](/user/213388) 有树套树的，常数太大了，CDQ常数很小
by _ChiFAN_ @ 2023-09-05 14:12:42
@[_bzy](/user/213388) 抱歉，某蒟蒻只想着水题(过倒是能过啦)了，根本没想最优解 awa
by 野生林登万 @ 2023-09-05 15:55:17
@[_bzy](/user/213388) https://www.luogu.com.cn/blog/yiw/solution-p1903
by zhouyuhang @ 2023-09-05 17:29:18
@[_bzy](/user/213388) <https://www.luogu.com.cn/blog/251Sec/solution-p1903>
by 251Sec @ 2023-09-06 12:42:12