如何用分块在线维护区间第 k 值？

ppip @ 2022-05-03 23:16:33

by Ginger_he @ 2022-05-03 23:20:20

@ppip 分块+值域分块

口胡的，错了别喷

by _•́へ•́╬_ @ 2022-05-03 23:21:39

@Ginger_he 主席树两只lg吧

by ppip @ 2022-05-03 23:22:11

@Ginger_he 具体维护什么信息啊

by _•́へ•́╬_ @ 2022-05-03 23:22:33

@ppip 似乎分块不能避免带lg

by YGB_XU @ 2022-05-03 23:30:40

@Ginger_he

具体维护什么信息啊

by Ginger_he @ 2022-05-03 23:32:23

@YGB_XU 好吧，我好像不会在线，谁让我那么菜呢

by yukari1735 @ 2022-05-03 23:33:39

@ppip 维护某个数出现次数和某个值域块中的数的出现次数的前缀。查询做差然后加入散块的信息。

by AC_Automation @ 2022-05-03 23:34:39

https://www.luogu.com.cn/problem/P5356

对于每个块维护其排完序的结果，修改时对零散块归并（或者直接暴力重构），查询时先二分答案，对于每个块内部再二分位置，边角暴力

by ppip @ 2022-05-03 23:41:25

@泉此方 这个前缀是块内的？

那我还是不会 O(\sqrt{n}) 查询

by yukari1735 @ 2022-05-03 23:42:45

@ppip 是的。