题目大意：给定一个环，每个节点有一个所属国家，k次事件，每次对[l,r]区间上的每个点点权加上一个值，求每个国家最早多少次操作之后所有点的点权和能达到一个值

首先我们考虑暴力想法

对于每个国家分开讨论 二分操作次数

但是这样每次Judge的时候我们要模拟1~mid所有的操作 浪费在这里的复杂度实在太大

这样做每个国家需要模拟O(klogk)次操作 时间复杂度O(nklogk) TLE

我们需要对浪费在这里的复杂度做一些改进

1.可持久化线段树(MLE)

每次二分一个mid之后 我们要找到mid次操作之后的版本

那么很容易想到可持久化线段树

这样每次二分到一个mid可以O(logm)得到值 时间复杂度O(klogm+nlogklogm)

残念的是我MLE了- - 本来以为写了标记永久化的线段树能省掉不少空间的- - 结果- -

内存池就算开了1500W也不够用 真是卡成狗- -

2.整体二分

不能从k下手，我们就要从n下手

二分Solve(x,y,S)表示答案落在[x,y]区间内的国家集合为S

将当前的修改调整至mid，将S集合分为两部分：答案落在[l,mid]的S1和[mid+1,r]的S2

对这两部分继续分治 直到x==y为止 统计答案 退出

时间复杂度O(nlogklogm) 此外注意30W*30W*10E会爆long long 所以我开成了double。。。
————————————————
版权声明：本文为CSDN博主「PoPoQQQ」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/PoPoQQQ/article/details/42263265

bzoj 2527

整体二分。

　　将所有的国家一起二分。

　　对于当前的答案区间[l,r]，先模拟下前mid场的流星雨，用树状数组维护。

　　再将已经超出目标pi的国家放到左边；把没达到目标的放在右边，并将这些国家的需求减去已经收集到的数量。

　　然后恢复刚才的流星雨，带上相应的国家，分别左右递归。

　　当访问到叶子节点的时候（即l==r），当前存的国家的答案即为l。