<h2>赛时</h2>
T1 一看暴力分是之前做过的原题，所以就粘写完了 $O(n^2logn)$ 的暴力，
T2 想了想，发现每次一定要把最小值移动到左边或右边，然后可以递归成子问题去做了
T3 建出来树之后只会暴力 dp。
最后 40+100+25 第三题挂了 20 分完美省三。
<h2>题解</h2>
<h3>A. Game</h3>
$O(n^2logn)$ 的做法是显然的：我们先贪心找出得分最高是多少，然后二分每一位放什么，贪心 check 就好了。
我们想如何快速维护这个贪心：我们可以用一棵权值线段树，记录答案，$a$ 的剩余数和 $b$ 的剩余数，合并用左边的 $a$ 去匹配右边的 $b$ 就好了。
时间复杂度 $O(nlog^2n)$
代码
<h3>B. Time</h3>
发现每次操作一定要先把最小值移动到边界上，然后就变成了一个规模为 $n-1$ 的子问题。
直接模拟就好了。
时间复杂度 $O(nlogn)$
代码
<h3>C. Cover</h3>
我们可以利用区间的包含关系建出一棵树，限制实际上就是每一条从根开始的链的节点数量不超过 $k$，考虑暴力 dp：设 $f_{i,j}$ 表示 $i$ 子树内到根选点最多的链的点数是 $j$，转移先合并子树，再考虑根对答案的贡献：
$$f_{i,j} = \max \{f_{i,j},f_{i,j-1}+a_i\}$$
然后优化有点神仙...我们考虑对每一个 $f_i$ 进行差分，那么发现这个差分序列 $g_i$ 一定是单调递减的（差分序列的意思是在原有的情况下选出最大的 $k=1$ 的情况）。我们的合并变成了直接按位相加，用根更新变成了在合适的位置插入 $a_i$。（对应了最优情况下差分表是递减的性质）
然后我们可以对于每个点开一个 set，长链剖分后直接暴力合并就可以了。
时间复杂度 $O(nlogn)$
代码
<h2>总结</h2>
T1 对于线段树的应用的理解还不是很到位。。其实某些结构在线段树上通过合并就能考虑到所有的情况。。比较神奇
T2 中间调了一会，要重点考虑有相同数的情况！（如果数据范围里没有提示估计我就挂了）
T3 有时候一种最优方案的性质（比如差分表单调递减） 可以变成构造这种最优方案的最优选择策略（每次新点加入到 set 的对应位置），感觉比较神奇CSP.rp++
