P6619 [省选联考 2020 A/B 卷] 冰火战士
对于一次战斗，冰火两方能量较少的那方会耗尽，答案为这个能量的两倍。
我们就是要找一个中间值，左边的冰战士能量值之和与右边火战士能量值之和最小值最大。
离散化，我们可以二分找到第一个冰的前缀和大于火的后缀和的位置 \(p\)，答案为 \(p-1\) 或 \(p\)。
怎么二分呢，考虑线段树上二分，然而常数过大，改成树状数组上倍增。
P2221 [HAOI2012] 高速公路
一般两两点的距离之和都是依靠计算边的贡献。于是我们求 \(\sum_{i=l}^{r-1}c_i \times (i-l+1)\times(r-i)\)。
拆式子 \(\sum_{i=l}^{r-1}c_i \times (ir-lr+r-i^2+il-i)\)，所以我们线段树维护 \(\sum c_ii^2,\sum c_i i,\sum c_i\) 即可。
线段树模板。
P4899 [IOI2018] werewolf 狼人
对于每个询问，我们找到一个 \(x\)，使得 \(s\to x\) 路径上最小值 \(> l\)，且 \(x\to t\) 路径最大值 \(<r\).
一个路径上最大值最小值考虑用 kruskal 重构树。
我们发现 \(s\) 点和 \(t\) 点，各找到有一个子树的 \(x\) 满足条件，然后如何判断有无交集呢？
我们扫描线，枚举其中一棵树的子树，用树状数组维护另一棵树哪一些点在前一棵树的子树里。