题解：AT_agc069_a [AGC069A] Schedule Optimization

有迹可循的好题。

考虑把操作树建出来，假设我不能操作怎么判断合法性。

对于一个非叶子节点，设左右儿子比赛出来的合法区间是 $[l_1,r_1]$ 和 $[l_2,r_2]$，那么两区间不交就无解，否则比赛后的合法区间为 $[\max(l_1,l_2),\max(r_1,r_2)]$。

一个很好的想法叫做只操作左端点，也就是当合并时发现 $l_1\leq r_1<l_2\leq r_2$ 时，把 $l_2\gets r_1$，因为左端点越小越好。但是这样是不对的，你不能一边合并一边做操作。

由于 左端点越小越好 和 合并时取 $\max$ 的矛盾，我们先不考虑左端点的操作，考虑只能对右端点做操作会发生什么。

一个点合并后的右端点就是子树内右端点最大值。证明很简单，你右移 $r_1$ 不会让 $\max(r_1,r_2)$ 变大。

所以我们考虑在叶子把左端点做好，在合并过程只考虑右端点即可。考虑 dp，设 $f_{x,i}$ 表示合并之后 $l\leq i$ 的最小代价。转移有

对于叶子节点 $x$ 有

容易发现 $f_{x,*}$ 是凸的，维护凸包折点即可。时间复杂度 $O(2^n\times n)$。