P16702 [MCO 2026] 雨水收集
解析
我们令 \(L_i=max_{j=l}^i h_j\)，\(R_i=max_{j=i}^{r} h_j\) 由于 \(max(L_i,R_i)=max_{j=l}^rh_j\) 为定值，那么考虑转化：\(\sum_{i=l}^r min(L_i,R_i)-h_i =(\sum_{i=l}^r L_i+R_i)-(r-l+1)*max(l,r)-sum(l,r)\)，后面两个都是直接用线段树就可以的，\(L,R\) 用单侧递归线段树即可
启发
\(\begin{cases} min(a,b)=a+b-max(a,b) \\max(a,b)=a+b-min(a,b) \end{cases}\)，在一者不好求时可以考虑转化成另一者
P5986 [PA 2019] Szprotki i szczupaki
解析
显然的吃法是先吃小的直到能够吃大的，吃完大的继续吃小的，这样每次重量至少翻倍，复杂度是 \(O(nlogk)\) 的，瓶颈在于吃小的的过程，对于这个过程我们可以线段树上二分优化，复杂度降为 \(O(lognlogk)\)
P9576 「TAOI-2」Ciallo～(∠・ω< )⌒★
还有起爆器
解析
我们令 \(l,r\) 为我们选取的端点，\(pre_i,suf_i\) 为公共前后缀长度（不一定最长），那么方案合法，必须满足：\(\begin{cases} r-l+1\ge m \\pre_i+suf_i \le m \end{cases}\)
我们发现瓶颈在于 \(pre,suf\) 的量级是 \(O(n^2)\) 的，实际上我们只需要用类似差分的思想，用树状数组维护，遍历 \(pre\)，在 \(maxpre\) 处减一即可
另外还需考虑T在S中的情况，但是是简单的