日记

一起把周六的日记也写了吧。

考试爆零。机房 rating $16.7 \to 13.7$，决心 $-\inf$。

T1 # Link to T1

神秘小 dp，没改，明天改。

T2 # Link to T2

想到了可持久化并查集，没想到和那个可持久化并查集一起的 Kruskal 重构树。

我这么菜不适合 Kruskal 这个英文名。

T3 # Link to T3

主席书双 $\log$ 做法还没调出来，单 $\log$ 做法待会再说。

但是我拿测速代码测了 cwoi 的机子每秒大概 $4.1 \times 10^8$，而 $3 \times 10^5$ 的双 $\log$ 也才 $1.1 \times 10^8$，没准双 $\log$ 卡卡常能过？

T4 # Link to T4

神经分讨。

考虑 $[l,r]$ 区间内的最大值 $a_x$ 出现在三个区间中的哪个位置。

• 中间
  显然中间对于答案的贡献无论如何都是 $a_x$，而两边的段随着长度的减小，贡献显然不会增加。那么最优方案就是 $a_l + a_r + a_x$。
• 左边
  显然左边的代价无论如何都是 $a_x$。根据上文的结论，第二个区间的长度越小贡献越小。所以整个段的答案就是 $a_x + \min\limits_{r' = x + 1}^{r - 1}\{a_{r'} + \max\limits_{i = r' + 1}^{r}\{a_i \}\}$。我们离线，从 $1 \to n$ 枚举每个 $r$ 及其对应的询问。设 $f_i$ 表示当前 $r$ 所对应的 $\min\limits_{r' = x + 1}^{r - 1}\{a_{r'} + \max\limits_{i = r' + 1}^{r}\{a_i \}\}$。用单调栈 + 线段树维护。具体而言是这样的：维护一个单调递减的单调栈。如果当前的 $a_r$ 把栈顶 $stk_{top}$ 弹出了，由于 $a_{stk_{top}}$ 是之前的 $r' \in [stk_{top - 1},stk_{top})$ 的 $\max\limits_{i = r' + 1}^{r}\{a_i \}$，现在被 $a_r$ 替换了，所以在线段树上的 $[stk_{top - 1},stk_{top})$ 区间加 $-a_{stk_{top}} + a_{r}$。还要单独更新 $r - 1$。枚举每个 $r_i$ 是当前枚举的 $r$ 的询问， 那么答案就是 $a_x + \min\limits_{i = x + 1}^{r - 1}\{f_i\}$，直接线段树区间查最小值就是了。
• 右边
  把整个序列翻转，然后做左边一样的就行。

后日谈 # Link to 后日谈

感觉我一事无成。