CF2031D Penchick and Desert Rabbit

很有意思，总结了三种做法。

Problem Link

简要题意

有 q 次询问，每次给出长度为 n\le 5\cdot10^5 的序列，称 i 与 j 是互相可达的当且仅当 i<j\ |\ a_i>a_j。问从每个位置 i 出发能到达的最大高度。

思路分析

赛时给出一种做法，赛后学到两种。不过 CF 的 Editorial 是最巧妙的，三种方法的方向几乎完全不同。

赛时做法

连通性问题首先考虑建边跑并查集。朴素想法是考虑一个位置向左一步能跳到的位置，但是这样建边复杂度是 O(N^2) 的。

发现很多边实际是冗余的，当一个位置 i 与其左边满足条件的位置并到一起后，之后的位置只需要连 i 左边最大的 h_x 位置就可以把他们全部并入一个块里。于是可以拿个 set 维护 i 左边 fa_i=i 的位置，每次 i 连边时只需要连 h>h_i 的位置，再把这些已经在一个块内的位置删到只剩一个即可。总复杂度 O(Tn\log n)。

赛时并查集不用 dsu 超时了一发，难绷。

Submission

？分段法

从同伴那学到的，感觉也很妙。

可以发现所有的跳跃都是若干次上图的折线跳跃或者折线的一部分。我们将上述折线分成“向右跳”和“向左跳”两部分。

考虑第二个绿色条 j 怎么更新到第一个绿色条 i。倒序扫描，将 j 的贡献记录在 [j+1,n] 中最低的点，再在 i 取出该贡献，可以用树状数组维护最大值实现该功能。具体地，维护后缀最小值 h_{\min}，在 j 处时修改树状数组上 [h_{\min}+1,n] 的最大值，在 i 处时取出 [1,h_i) 的最大值，就能实现如图折线跳跃的情况。

这时候再考虑如何求图中红色条的最值，正序扫描，类似上面的情况处理即可。

Editorial

考虑 i 能否到达 i+1，若能跳到必然要么是 h_i>h_{i+1}，要么是先从 i 向前跳到某个高于 h_i 的位置 j，再从 j 向后跳到 i 后的某个位置 k，最后从 k 跳到 i+1。

因此维护前缀最大值和后缀最小值，再扫描转移即可，复杂度是可喜的 O(Tn)。

Submission

真是妙妙妙极了。