题解：CF2031D Penchick and Desert Rabbit

怎么赛时这么多人写优化建图呢。这不是我们模拟赛题的结论吗。

首先边可以看成双向边。

结论：若 x,y 连通，则 \forall i\in(x,y)，i 在 x,y 的连通块中。

证明：

第一种情况：a_x>a_y。若 a_x>a_i，x 和 i 相连；若 a_i>a_y，i 和 y 相连。不可能两个条件都不满足。

第二种情况：a_x\le a_y。此时要满足 x,y 连通，必须存在 j\in[1,x)，a_j>a_x，或者存在 j\in(y,n]，a_y>a_j。如果 a_i\not\in[x,y]，与第一种情况类似，能连到 x 或 y。如果 a_i\in[x,y]，可以和 j 连通，而 j 又与 x,y 连通。

故连通块是一个区间，即一个点要么与前一个连通块相连，要么新开一个连通块。

我们只关心 i 与 i-1 的连通情况，即新开连通块的条件是不存在 j\in[1,i-1)，a_j>a_{i-1}，也不存在 j\in(i,n]，a_i>a_j。

简化一下，就是 \max\limits_{j=1}^{i-1}a_j\le\min\limits_{j=i}^na_j，求个前缀 max 和后缀 min 即可。

时间复杂度 O(\sum n)。