这两道题都是十分具有 JOI 风格的数据结构题。

都没有完全做出，不过确实感受到了数据结构的妙处和水平的提升。

loj 3033 两根天线

题意： https://loj.ac/p/3033

不妨设 ，那么两根天线之间的限制为

使用 cdq 分治+线段树处理这些偏序限制即可拿到除最后一个包的所有分。

然后笔者卡在了这里，一直没有想到好的办法处理这些限制。

考虑把节点 拆成两个事件，在 处出现，在 处消失。

那么我们从小到大扫描 ，并同时维护每个 的最大成本 。

一个询问的答案就是在 时的 。

我们不妨假设 ，因为最后是求 的最大值，我们把 变为原来的相反数再做一遍就不会漏统计了。

此时绝对值就被去掉了。更方便的是，我们并不需要考虑 这个限制，因为 的肯定不会被算入答案。

那么此时，设 表示，如果 目前出现了且没有消失，那么 ，否则 。

扫到一个 的时候就是把所有在 中且出现了的 的 值对 取 。

在线段树上维护 和 ，维护一个标记表示从上次 pushdown 到现在，这个节点被操作的 的最小值，就可以维护了！

本题的难点主要在于这个扫描线，想到了之后其实不难使用这种线段树技巧完成维护。扫描线作为一种较为轻工业的数据结构技巧，其运用更加考验思维能力。

代码： https://loj.ac/s/1803371

loj3034 两道料理

题意： https://loj.ac/p/3034

首先显然有一个 的 DP。

设 表示第一道菜做了前 个部分，第二道菜做了前 个部分，设 ，那么容易得出转移式：

考虑优化这个 DP。

我们枚举 ，同时维护 。

我们注意到 只会从 以及上一个时刻的 转移，这启示我们考虑差分数组 。

那么，转移式子中的 ，就相当于对 的 整体加上 ，也就是

那后半部分怎么办呢？设 。

我们的操作相当于将每个 与 取 。

但是我们发现，此时 的值并没有改变，但 的增大会使得 往后的 值都变大，所以我们要在 减去 变化前后的差值。

这还是不好处理。

考虑 ，我们对 的操作变成：

1. 单点加
2. 在 递增的过程中，每个 都会从 变成 ，在恰好从 变到 的这一刻， 要加上 。
3. 如果 ，让 。

我们发现 的 并没有什么用， 操作中的 完全可以改写为 ”下一个 的位置“。

注意到 操作最多新增 个 的 ，而一次 操作必定减少 个。

所以我们用个 维护所有 的 即可，每次暴力修改所有涉及到的 ，易证只会修改 次。

时间复杂度 。

代码： https://loj.ac/s/1803767