P5044 [IOI2018] meetings 会议
对于 \(h_i\le 20\) 的数据，我们每个点维护单调栈，其代价为 \(x\) 的时候，取的位置是一个区间。
很显然已经有一个莫队算法，支持区间加，区间查询即可。然而不优。
其实单调栈与笛卡尔树是相似的，考虑建出笛卡尔树。
我们假设就对 \([l,r]\) dp，那么取出最大值，如果在左边取址，那么右边的贡献都是这个最大值。
右边取址同理，设 \(f_{u}\) 表示 \(u\) 子树内最小的代价，转移很容易。
具体地，把 \(u\) 左右儿子拿出来，取 \(\min(f_{ls}+A_u\times \min(siz_{rs},r-u),f_{rs}+A_u\times \min(siz_{rs},u-l))\).
转移方程里有 \(l,r\)，非常难办。不妨把 \(l,r\) 放进状态里面。当我们找到 \(l,r\) 的 lca 时，从这里开始 dp。
这样的话，lca 下每个点都只有一侧是被 \(l,r\) 所限制的。
考虑怎么维护 \(f_{u,x},g_{u,x}\) 分别表示 \(l=x\)，\(r=x\) 时的答案。同时设 \(h_u\) 表示原来的 \(f_u\).
\(f_{u,x}=\min(f_{ls,x}+A_u\times siz_{rs},h_{rs}+A_u\times (u-x))\)。\(g\) 同理。
这样，我们需要支持区间加等差数列的，还要有区间 checkmin 的线段树。
checkmin 是可以换成推平的，不难观察到 \(\min\) 中后者随 \(x\) 增加而减小，二分出其起效的位置，推平。
P10430 [JOISC 2024 Day1] 鱼 3
我们相当于选出一个 \(\sum k\) 最小的递增的 \(\{c_i-kD\}\) 数列。
由于对于固定左端点，右端点的答案是可以增量的维护出来的，所以我们递推右端点做扫描线。
对于加入的一个右端点，我们从后往前扫，使得前面都变成递增，这么做的话复杂度是 \(O(n^2)\)。
我们要考虑找性质进行优化。
不难发现，若一个位置减少，导致其前一个位置减少，那么他们以后都会一起减少。
我们可以用并查集把这些同时发生改变的并起来。然后接下来的处理用线段树维护区间和即可。
P2605 [ZJOI2010] 基站选址
你可以求出每个村庄被覆盖，哪些村庄放基站即可做到，那么这是一些区间。
然后我们再设计一个 dp，\(f_i\) 表示上一个是在 \(i\) 处放置的答案。
假设从 \(i\) 转移到 \(j\)，那么我们可以知道上一个填 \(i\)，区间填到了多少个。
对于左端点 \(\le j\) 且右端点 \(\ge j\) 的我们可以覆盖掉，右端点 \(\le j\) 的我们需要给补偿。
考虑用线段树维护 dp 过程，线段树维护每个 \(j\)，从 \(j\) 转移的代价，转移取 \(\max\)。
考虑 dp 从 \(i-1\) 递推到 \(i\) 会发生什么。我们从此覆盖不了右端点为 \(i-1\) 的区间。
对于一个区间 \([l,i-1]\)，那么若从 \([1,l]\) 转移，代价需要增加，所以区间加即可。
P9546 [湖北省选模拟 2023] 山路长环 / ring
我们先思考一个问题就是什么时候先手会必胜或必败。
先考虑链的情况。简化问题变为只有两条边，如果初始在边上两个点就是无论如何必败，中间必胜。
所以如果是三个边，分讨中间点和边上点的话，无论如何必胜；
如果四条边呢？如果在边上，第一个点和第三个点都是必败态，这与两条边形式相同，所以必败。
后面同理。所以我们得出，一条链的胜负态只与奇偶性有关。
如果是环呢？如何环的大小为奇数，那么先手直接断一条边就赢了；为偶数，谁先断边就输了。
那么双方的操作肯定都是把边减成 \(1\)，直到存在一个 \(1\)，就输了。
这个直接用线段树维护，秒了。