【解题报告】JOISC 2019 Day3

~~咦，Day 2 怎么消失了~~

「JOISC 2019 Day3」指定城市

$E=1$ 的时候可以换根 $\text{dp}$；$E=2$ 的时候也可以树形 $\text{dp}$。

可以证明，当 $E>2$ 的时候，贡献是凸的，而且 $E$ 的方案一定包含 $E-1$。因此只需要在 $E=2$ 的基础上，把树类似长链剖分，每次取贡献最大的长链即可。

时间复杂度 $\mathcal{O}(n\log n)$。

三个操作中前两个赋值看起来比较相似，易于证明存在一种最优方案可以先只赋值，后面只 $\text{flip}$。

把一个状态的 $01$ 交接点拿出来，则一个 $\text{flip}$ 恰好可以消去/增加两个交界点，因此最后计算两个状态的交界点的对称差，若剩下 $s$ 个，则最后还需要 $\left\lceil\dfrac{s}{2}\right\rceil$ 个 $\text{flip}$。

设 $\text{dp}_{i,0/1/2}$ 表示前 $i$ 个元素，最后一个元素被变成 $0/1$ 或者不变，对称差交界点个数的最小值。一次操作可以当作两个对称差交界点，也就是把 $\text{dp}$ 值 $+2$。

首先把时刻 $i$ 的时间 $-i$，这样走一步可以看作不花费时间。

如果要经过一个点，有两个分段函数：$f(t)$ 表示 $t$ 时刻进入之后，什么时候会出来；$g(t)$ 表示 $t$ 时刻进入，需要花费多少代价。

$f(t)$ 的形式肯定是前后两段平，中间 $f(t)=t$；$g(t)$ 是前面平，后面一次函数。合并两段的时候，由于 $f(t)$ 是单调的，所以 $f'(f(t))$ 也是单调的，还是类似的形式；$g(t)$ 会加一个截距，但后面一次函数的形式保持不变。

因此可以线段树维护折线，$\mathcal{O}(n\log n)$。