求教这个题有没有靠谱的在线做法

damocris @ 2023-06-15 23:06:03

by jijidawang @ 2023-06-16 07:43:10

强于区间历史 k-th？

by Querainy @ 2023-06-16 08:26:18

在值域线段树上二分，每个点开一个主席树支持矩形数点，复杂度O((n^2+q)\log^2 n)。就是题解区某个整体二分的直接在线化。

by damocris @ 2023-06-17 06:39:57

@华山抡剑 内存空间爆了吧

by Querainy @ 2023-06-17 07:28:07

@damocris 但是可以卡啊。先\log大小分块，块间主席树只有5层，块内爆力分散层叠，这部分空间是一个\log，然后外层值域线段树高\log\log层可以扔掉，低\log\log层可以扔掉，这样它只有10层，但是还是不够，所以换成四叉的，这样它只有5层。主席树每个点需要记左儿子，右儿子，区间和，一共12个byte，算一下大概是刚好够的!

by Querainy @ 2023-06-17 11:37:23

@damocris 不用卡了。我去学习了一下怎么做到O(n\log n)空间。https://www.luogu.com.cn/blog/uakioi/linear-space-mergesort-tree

by Querainy @ 2023-06-17 11:56:11

shaber。假了。等我修一下。

by Querainy @ 2023-06-17 12:01:08

修好了。

by damocris @ 2023-06-17 16:42:36

@华山抡剑 厉害人

by Daniel1234 @ 2023-11-23 15:56:30

@damocris 在尝逝能不能分块过，已经交了460发了（