Tricks
一点点显然但是会忘记的东西。
结论题，事实上很多时候贪心全选是对的。
扫描线
P7530 [USACO21OPEN] United Cows of Farmer John P
没地方写导致的 \(qwq\)。
我们发现大致要写一个麻烦的偏序，但是如果我们维护一个扫描线，仅仅更新能更新的地方，就是我们不关心后继，扫到新的撤销前驱即可，所以我们可以变成类二维数点问题，写一棵维护系数的线段树即可。
大致上是在新的地方往前驱以前都加一，撤销前驱的系数即可。下面有形式化的代码。
P5926 [JSOI2009] 面试的考验
考虑偏序挂点。
考虑往某个点挂上 \((i, a_i)\) 假设我们已经在 \(a_x\) 上挂上去了，我们发现如果要在 \(a_y\) 上挂上要满足 \(a_y - a_i > a_x - a_y \to a_y \leq \frac{a_i + a_x}{2}\)。
那么值域就满足折半，即只有 \(\log n\) 个点，算出来即可。
分治，关键字 “除开一项的所有”
CF1442D Sum
妈的，学这么多年终于学到了！！
结论：必然全选完数组，然后剩下的选一个单个的。
证明：考虑选出数组，\(a\), \(b\) 若都没选完，那么考虑选更牛逼那个接在后面。
但是我们咋做那个？
考虑分治，求 \([l, mid]\) 时先插 \([mir + 1, r]\) 或者求 \([mid + 1, r]\) 先插 \([l, mid]\) 即可。
事实上，不如线段树分治。
选取若干路径的问题
或者是 XOR，那个题是点边转化。
[AGC010C] Cleaning
这一类问题考虑从子树内连上去的和子树外的。
不妨设子树外的决策为 \(f_x\)，这个一般要记下来。
那么考虑到 \(\sum f_y\) 这是子树内连出去的，那么可以计算出 \(f_x = 2a_x - \sum f_y\) 这些是经过这个 \(x\) 这个点的。
接下来除了这个，还要考虑子树经过 \(x\) 匹配的问题，这个问题考虑最大值是否超过一半即可。
可以归纳证明。