清橙 A1318 加强版：Almost
题意：
原版：\(n \leq 1e5, q \leq 3e4, TL 5s, ML 256G\)
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。加强版1：\(n,q \leq 1.5e5, TL 5s, ML 256G\)
加强版2：\(n,q \leq 1.5e5, TL 5s, ML 1G, 强制在线\)（由于空间变大所以严格来说不算加强版……）
思路：
原版
加强版1
首先考虑能否分数规划。
那么要判定
\(\frac{\sum A}{n-1}\geq R\)
变形
\(\sum A\geq R\cdot(n-1)\)
\(\sum A−R\cdot n\geq−R\)
\(\sum (A_i−R)\geq−R\)
接下来先不管强制在线，考虑整体二分。
那么在整体二分的当前轮中，我们对于每个询问有一个二分的\(Mid\)值。
显然我们应该按\(Mid\)从小到大（反着来当然也行）处理。
问题转化为：一个数列，支持全体加正数，和查询区间最大子段和。
先建出线段树，在每个结点我们统计“在结点对应区间内，且以区间中心为一个端点”的所有子段。（不妨称作“单侧子段”）
对应区间长度为\(len\)的结点，单侧子段有\(O(len)\)个。
进而考虑“在结点对应区间内，且过区间中心”的子段（不妨称作“完整子段”）。
易见最优的完整子段由两侧最优的单侧子段拼成。
两侧最优的单侧子段只会变化\(O(len)\)次，故需要考虑的完整子段是\(O(len)\)个。
不止如此，结点里还要统计所有后代的完整子段，于是所有结点统计的完整子段共有\(O(n log^2 n)\)个。
注意到一个子段的和是关于全局增量\(\Delta\)的一次函数，于是不妨对每个结点统计的完整子段求凸包。
观察：由于斜率只有\(O(len)\)种，故每个结点的凸包大小是\(O(len)\)，总大小\(O(n log n)\)。
随着\(\Delta\)的增加，我们在每个结点里维护一个扫描线就能查到“在结点对应区间内”的最优子段。
回答询问时会把区间拆成\(O(log n)\)个线段树区间，如何合并？
对每个线段树区间维护“内部最优子段”、“以两侧边界为端点的内部最优子段”，然后类比贪心求最大子段和的方法合并出答案。
单次询问\(O(log n)\)，整体二分中有\(O(n log n)\)次询问，时间共\(O(n log^2 n)\)。
空间即凸包大小总和，\(O(n log n)\)。
加强版2
强制在线？
需要抛开扫描线才行。
注意到问题分为两个部分：
1、每个线段树区间的“内部最优子段”
2、每个线段树区间的“以两侧边界为端点的内部最优子段”
每个部分，原先维护的扫描线都会有\(O(n log n)\)个“关键点”，每碰到一个关键点，某个结点的答案就要改变。
由于不能用整体二分，所以不能依赖扫描线来找到每个结点当前的关键点。
不妨在每个结点里同时存储所有后代的关键点，把这些点排序后标明，是自己的关键点，还是左儿子的，还是右儿子的。
以下的“关键点”就指代经过这番扩展后的关键点了。
那么回答询问，先在根节点里二分找到\(\Delta\)对应的关键点，然后用Wavelet Tree的方法，不断把当前结点的关键点编号对应上儿子的关键点编号即可。
Wavelet Tree的方法？很简单，就是对自己的每个关键点，预处理“他是第几个来自左/右儿子的关键点”。
时间不变，空间\(O(n log^2 n)\)，但因为空间常数很小所以1G存的下。
代码：
咕咕咕
这东西我能写一年
