题解：灯带问题
问题分析
对于电压 $x$，第 $i$ 个灯亮起当且仅当 $a_i < x$。发光段是极长的连续亮灯区间。
设 $f(x)$ 为电压 $x$ 时的发光段数量。我们需要支持：
- 修改某个 $a_p$
查询最小的 $x$ 使得 $f(x) \geq k$
关键观察
$f(x)$ 仅在 $x = a_i + 1$ 处发生变化（灯 $i$ 恰好在此时亮起）。
考虑 $f(x)$ 的表达式： $$f(x) = [a_1 < x] + \sum_{i=2}^{N} [a_i < x \leq a_{i-1}]$$
其中 $[P]$ 在 $P$ 为真时取值 $1$，否则 $0$。
对于 $i \geq 2$，项 $[a_i < x \leq a_{i-1}]$ 仅在 $a_i < a_{i-1}$ 时非零，此时它对 $x \in (a_i, a_{i-1}]$ 贡献 $1$。
计算变化量
在临界点 $x = a_j + 1$ 处，$f$ 的变化量 $\Delta f(j)$ 为：
$$\Delta f(j) = [j=1] + [j \geq 2 \land a_j < a_{j-1}] - [j \leq N-1 \land a_j > a_{j+1}]$$
解释：
$[j=1]$：第一个灯亮起时，产生新段
- $[a_j < a_{j-1}]$：当 $a_j < a_{j-1}$，灯 $j$ 比灯 $j-1$ 先亮，产生新段
$-[a_j > a_{j+1}]$：当 $a_j > a_{j+1}$，灯 $j+1$ 比灯 $j$ 先亮，灯 $j$ 亮起时连接两个段，段数减 $1$
数据结构
将所有可能的临界点 $a_i + 1$ 和所有修改中的 $v + 1$ 离散化。
建立线段树，维护每个离散化位置上的 $\Delta f$ 值。线段树节点存储：
sum：区间总和
max_prefix：区间最大前缀和
查询操作：找最小的 $x$ 使 $f(x) \geq k$，等价于找最小下标使前缀和 $\geq k$。利用 max_prefix 在线段树上二分，时间 $O(\log N)$。
修改操作：修改 $a_p = v$ 只影响位置 $p-1, p, p+1$ 处的 $\Delta f$ 值。先减去旧值，更新 $a_p$，再加新值。每次影响 $O(1)$ 个位置，时间 $O(\log N)$。
正确性证明
引理 1：$f(x)$ 是分段常数函数，仅在 $x = a_i + 1$ 处可能变化。
证明：灯 $i$ 的状态在 $x = a_i + 1$ 处从灭变亮，其他时刻不变。因此 $f(x)$ 仅在此时刻可能变化。∎
引理 2：$\Delta f(j) = [j=1] + [j \geq 2 \land a_j < a[j-1]] - [j \leq N-1 \land a_j > a_{j+1}]$。
证明：在 $x = a_j + 1$ 处，灯 $j$ 亮起。若 $j=1$ 或 $a_j < a_{j-1}$，灯 $j-1$ 未亮，产生新段，$+1$。若 $j=N$ 或 $a_j \leq a_{j+1}$，灯 $j+1$ 未亮，不影响。若 $a_j > a_{j+1}$，灯 $j+1$ 已亮，灯 $j$ 亮起连接左右两段，段数减 $1$。∎
引理 3：对于任意 $x$，$f(x) = \sum_{j: a_j + 1 \leq x} \Delta f(j)$。
证明：由引理 1，$f(x)$ 从 $f(0)=0$ 开始，在每个临界点 $a_j+1$ 处增加 $\Delta f(j)$。累加即得。∎
引理 4：修改 $a_p$ 只影响 $\Delta f(p-1), \Delta f(p), \Delta f(p+1)$。
证明：$\Delta f(j)$ 仅依赖于 $a_{j-1}, a_j, a_{j+1}$。修改 $a_p$ 只可能影响 $j \in {p-1, p, p+1}$ 的表达式。∎
定理：对于每次查询 $2\ k$，算法输出最小的 $x$ 使得 $f(x) \geq k$，或 $-1$。
证明：由引理 3，$f(x)$ 等于临界点 $\leq x$ 的 $\Delta f$ 之和。线段树维护了这些 $\Delta f$ 的前缀和。find_first(k) 返回最小下标 $i$ 使前缀和 $\geq k$，对应临界点 $c_i$ 即为最小 $x$。若最大前缀和 $< k$，则不存在满足条件的 $x$，输出 $-1$。∎
复杂度分析
离散化：$O((N+Q)\log(N+Q))$
- 初始化：$O(N \log N)$
- 每次修改：$O(\log N)$
每次查询：$O(\log N)$
总时间：$O((N+Q)\log(N+Q))$
空间：$O(N+Q)$
这段代码并没有枚举所有 (x,y)，而是枚举一组能够“支配”所有其他方案的候选方案：对于任意未枚举的划分，都能找 到一个枚举到的方案，其补人数不更多。
设三个组原有的人数为：
[ (L,M,H),\qquad L+M+H=n ]
人数为 (v) 的组至少还要补：
[ f(v)=\operatorname{bit_ceil}(v)-v ]
其中 bit_ceil(0)=1，正好表示空组需要补 1 人。
1. 外层循环枚举所有可能的轻量级人数
在 main.cpp:36 的循环开始时：
sum = bucket[0] + ... + bucket[i - 1];
也就是：
[ sum=#{a_k<i+1} ]
因此可以理解为令：
x = i + 1; L = sum;
由于同一体重的人不能被边界拆开，真正有意义的轻量级人数只有这些完整体重桶的前缀和，外层循环全部枚举到了。
L=n 等所有人都在一个组的边界情况，由初始答案：
int ans = least_add_to_pow2(n) + 2;
处理，即另外两个空组各补 1 人。
2. most 表示合法分界点
可以把所有人按体重排好序。代码没有真的排序，而是通过 bucket 构造：
most[pos] = 该位置所属体重段的起始下标
例如排序后的体重为：
1 1 3 3 3 5
则：
位置： 0 1 2 3 4 5 most： 0 0 2 2 2 5
所以：
most[k]
就是不拆开同体重人群的情况下，不超过位置 k 的最大合法前缀分界点。
在轻量级人数为 sum=L 时：
most[L + p] - L
就是不超过 p 的最大合法中量级人数。
3. 为什么只枚举 (p=1,2,4,8,\dots)
关键代码是：
for (int j = 0; 1 << j < n - sum; j++)
也就是只枚举：
[ p=2^j ]
这是因为最终每个组都要扩充到 2 的幂。
假设某个最优方案的中量级人数为 (M)，令：
[ p=\operatorname{bit_ceil}(M) ]
那么 (p) 一定是 2 的幂，并且：
[ M\le p ]
代码针对这个 (p) 选择：
[ M'=\text{不超过 }p\text{ 的最大合法中量级人数} ]
也就是：
M' = most[L + p] - L;
因为原来的 (M) 本身就是一个合法分界点且 (M\le p)，所以：
[ M'\ge M ]
同时又有 (M'\le p)，因此：
[ \operatorname{bit_ceil}(M')\le p =\operatorname{bit_ceil}(M) ]
中量级最终需要的容量不会增加。
另一方面：
[ H'=n-L-M'\le n-L-M=H ]
所以重量级人数减少，其最终需要扩充到的 2 的幂也不会增加：
[ \operatorname{bit_ceil}(H') \le \operatorname{bit_ceil}(H) ]
因此，从任意方案的 (M) 出发，都可以移动到代码枚举的 (M')，且总补人数不会变多。
这就是为什么只考察每个 2 的幂附近的最大合法分界点已经足够。
4. 当对应的 2 的幂超过剩余人数
如果：
[ p\ge n-L ]
那么循环不会访问 most[L+p]，因为会越界。此时直接把剩下的人全部放入中量级，重量级为空：
ans = min(ans, least_add_to_pow2(sum) + least_add_to_pow2(n - sum) + 1);
对应：
[ (L,n-L,0) ]
最后的 +1 是给空的重量级补一个人。
这同样不会比原方案更差：剩余全部人数也不超过那个目标 2 的幂，而重量级空组只需补 1 人。
总结
代码覆盖答案的逻辑是：
- 外层枚举所有合法的轻量级前缀人数 (L)。
- 对于固定的 (L)，最终中量级容量必然是某个 (2^j)。
- 对每个 (2^j)，选择不拆开相同体重的最大合法中量级人数。
- 任意其他分界都能被这样的候选方案替代，而且所需总容量不会增加。
剩余人全部进入中量级、以及所有人在同一组等边界情况被单独处理。
所以它枚举的不是所有划分，而是“所有可能成为最优解的代表划分”，复杂度为：
[ O(n\log n) ]