日记

我寻思我也不蠢哪？

Itinerary# Link to

谁说不蠢？

我们发现，一个路径合法当且仅当：对于 $\forall i \in [2,n]$，把 $a_{i - 1} \to a_i$ 路径上的每条边权值 $+1$，最终没有一条边的权值 $\gt 2$ 就是了，可以直接树剖 $+$ 线段树。

而对于从点 $i$ 开始是否合法呢，我们直接把 $i \to a_1$ 的这条路径上的边也全部 $+1$ 看看合不合法就是了。

Curtains# Link to

其实紫题还是要难一些哈。

我们看到标签里有“离线”，于是我们就想到先把询问离线。我们从大到小枚举每个 $l$，用线段树维护 $a_r$ 表示只用左右端点都在 $[l,r]$ 内的线段，从 $r$ 开始向左连续的最远位置。

我们发现对于一条线段 $[l,x]$，他可以对所有的 $\ge x$ 的 $r$ 且 $a_r \le x + 1$ 的 $a_r$ 都有 $a_r = \min(a_r,l)$。于是我们直接掏出吉司机线段树，时间复杂度 $O(n \log^2 n)$，居然能跑过 $5 \times 10^5$。

后日谈 # Link to 后日谈

萨尼铁塔让我不要剧烈运动，那我得肥成啥样啊？