P2468 [SDOI2010]粟粟的书架 题解

· · 题解

这里是一篇整体二分乱草主席树的题解，有效防止 MLE，且只多了一只 log，理论适用于比主席树更大的数据范围。

比较明显的是本题只需找到一个位置 k，使得区间前 k 大的数前缀和大于等于 H_i，关于矩阵中区间第 k 大/小系列问题，考虑使用整体二分。

与板子 P1527 相同的手法，由大到小逐个加入矩阵中的数，要记录的是区间和与区间排名，使用二维树状数组单点加，区间查，是 trivial 的。

对于整体二分结果，区间和已达到目标的扔到左边，未达到的减去左边的影响，达到的扔到右边，同时答案把左边部分的排名贡献加上，要注意最后输出答案还需要加上自己的一个贡献。

关于判定无解，直接无脑先全加入，然后判断还没达到的就是无解即可。

另外空间需要准备两种情况的空间，导致要写双份代码，评价为芜马。

code