11.2

T1 一个ezDP

注意到区间端点取在max/min处不劣 考虑转移时分开l/r

或者维护y=x+b和y=-x+b的凸包转移？

别的就不太会了，大战T2无果。

11.3

T1 诈骗提

没想到反悔贪心，显然可以简图跑网络流。 不是，Dinic和ISAP怎么都78只跑45pts???

正解考虑建立无向图跑欧拉回路

具体的，先判掉度数为奇数的，考虑在原图上走欧拉回路，在建边时记录正、反边，在走反边时记录，即为翻转。 由于可将有向边起点看成上，终点看成下，故二者等价。

T2 反悔贪心

考虑维护每个人最早、晚安抚时间。

显然\(a\)是定的，在\(b>0\)时尽量后选，在\(b<=0\)时尽量先选。

但这样会有冲突。

于是再对b>0的维护栈：

把已处理的位置划成若干连续分组，每组内所有人使用相同的时间。

最前面可能有一个“基准组”，时间固定为 L，不存进栈。

其余各组的起点为：

s[1] < s[2] < ... < s[m]

栈中保存这些起点。整组系数和就是这一组所有 b 的和

因为 R 单调不减，所有分组时间也单调不减。

一个组内任意位置 j 都满足 j >= s[x]，故 R[j] >= R[s[x]]；将整组安排在 R[s[x]] 不会超过任何人的上界。

栈内每个分组的系数和严格为正。

在遇到b<0时，考虑弹出栈顶还是入栈收益大即可。

注意树可能不会安抚任何人或者最右一个\(i\)满足\(p_i != -1\)之后的人，要动态维护这一段的max。