专栏文章

题解：CF2031D Penchick and Desert Rabbit

rran_qwq
CF2031D题解参与者 3已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@mir428b4
此快照首次捕获于
2025/12/04 15:25
3 个月前
此快照最后确认于
2025/12/04 15:25
3 个月前
查看原文
怎么赛时这么多人写优化建图呢。这不是我们模拟赛题的结论吗。
首先边可以看成双向边。
结论：若 x,yx,y 连通，则 ∀i∈(x,y)\forall i\in(x,y)，ii 在 x,yx,y 的连通块中。
证明：
第一种情况：ax>aya_x>a_y。若 ax>aia_x>a_i，xx 和 ii 相连；若 ai>aya_i>a_y，ii 和 yy 相连。不可能两个条件都不满足。
第二种情况：ax≤aya_x\le a_y。此时要满足 x,yx,y 连通，必须存在 j∈[1,x)j\in[1,x)，aj>axa_j>a_x，或者存在 j∈(y,n]j\in(y,n]，ay>aja_y>a_j。如果 ai∉[x,y]a_i\not\in[x,y]，与第一种情况类似，能连到 xx 或 yy。如果 ai∈[x,y]a_i\in[x,y]，可以和 jj 连通，而 jj 又与 x,yx,y 连通。
故连通块是一个区间，即一个点要么与前一个连通块相连，要么新开一个连通块。
我们只关心 ii 与 i−1i-1 的连通情况，即新开连通块的条件是不存在 j∈[1,i−1)j\in[1,i-1)，aj>ai−1a_j>a_{i-1}，也不存在 j∈(i,n]j\in(i,n]，ai>aja_i>a_j。
简化一下，就是 max⁡j=1i−1aj≤min⁡j=inaj\max\limits_{j=1}^{i-1}a_j\le\min\limits_{j=i}^na_j，求个前缀 max 和后缀 min 即可。
时间复杂度 O(∑n)O(\sum n)。

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...