CQ-S00666 出击 CSP 最终嘟嘟嘟嘟！？
paper_
·
·
生活·游记
（省流：大概 AK 了，如果引起了您的不适，非常抱歉qaq）
选择题。将标题中的“嘟嘟嘟嘟”换为下列哪一个选项最合适？（4分）
---
### 往期回顾
CSP2023，这个人的第一次 CSP，初学 OI 的我在这一年拿下了 -J $380$ 却在 -S 中一败涂地。幸运的是连三等都没有拿到，成功没有成为我参赛记录中的一个污点。
CSP2024，这个人小有所成，放弃了 -J 直接梭哈 -S，最终切掉 T123 斩获 $336$，给了年幼的蒟蒻很大的信心。
CSP2025，这个人已经要上天啦，他表示窝初三都能 $336$，今年不得 AK？最终成功做不出来 T3T4，喜提 $288$，并且清楚地认识到了自己是个区的本质。幸运的是卡线去 WC 玩了。
CSP2026，这个人已经高二了，再不 AK CSP-S 可能这辈子就没有 AK NOI 系列赛事的机会了。但是没关系，今年窝开了（？），CQ-S00666 这个考号就可以证明窝的手段！哼哼，小小 CSP，看窝一雪前耻！
---
### Day -8
拿到准考证了，CQ-S00666。
尝试绷住最终失败。
### Day 1
进行了非常多的睡觉，感觉有点睡困了，14:00 进入校门。
入场发现很多人都在打火车头，反观这个人，趴在桌子上睡觉，难道是因为他开了所以有恃无恐/jy
开题，3min 切掉 T1，比较顺利。
T2 怎么是是？阅读题面 15min 后依然不懂地铁是单向还是双向，因为神人题面一直在强调“地铁**依次**经过……”，最终观察样例发现单向地铁不符合两两互通的限制遂开写，差不多 15:00 通过。
好好好，3.5h 做 T3T4，优势在我，浅浅看了一眼，好像都是 DS？有点小炸（事实证明有 $0$ 道 DS/ll）。
T3 先糊了一个令 $ne_i$ 表示 $i$ 能到的最远点，然后使用主席树之类维护 $ne_i\to i$ 的变化的做法。发现空间炸了，狂卡空间。发现假完了，调不出来，倒闭。我好像梦回 2025T3 了。欸，我去，那我包想复杂了呀！想通这一点后主播直接删掉代码重新开始想。
发现 $(x,y)$ 合法当且仅当，$x$ 贪心（指每次跳最远点）跳到 $y$ 的序列和 $y$ 跳到 $x$ 的序列仅有一个位置不同且该位置的下标之差为 $1$。
枚举这个下标，简单维护一下就 $O(n)$ 了。
怎么只有 1.5h 了，赶紧上个厕所。
主播心理 belike：不慌，我都开了，1.5h 随便过 T4 好吧。
看题，感觉是二分，然后发现叶子是没用的。
这里的意思大致是假设二分出来的答案为 $mid$，令 $d_i$ 表示最终方案中至少要有一个与 $i$ 距离 $\le d_i$ 的点，初始所有 $d_i$ 都为 $mid$。发现如果一个叶子的 $d_i>0$ 那么直接将这个叶子删掉然后对叶子的父亲 $chkmin(d_i-1)$ 一定是不劣的。
然后窝瞪眼一看，现在所有叶子都是 $d_i=0$ 了，所以所有叶子都要选，如果只能选一个连通块那么就相当于所有点必选了。只能选两个连通块不就是只能有虚树上的一条边不选了嘛！？枚举这条边，边的选择情况一定是 $1110001111$ 的样子，$O(len)$ 做是简单的，$O(\sum len)=O(n)$。
5min 秒了，难道我真的开了？
发现虽然正常虚树是 $O(k\log k)$ 的，但是窝一次二分只做一次虚树，所以可以直接 $O(n)$。总复杂度 $O(n\log n)$。
代码也很简单，总之就是没什么压力地写完了。
---
检查一遍后开始胡思乱想。
教练考前给我们介绍了 ber 中的魔咒之一：CSP 打的好 NOIP 一定会打爆。（其余魔咒类似 WC 打的好省选一定会打爆， APIO 打的好 NOI 一定会打爆[流汗黄豆]）
主播表示根本不慌，我如果 AK 了那也是因为我开了，开了再 AK 根本不会消耗 RP；如果没 AK 那就是挂分了，意料之外的挂分会积攒 RP。总的来说是我赢麻了😎
---
最后来揭晓选择题答案。
$A$ 选项：AK 了，所以并没有一败涂地。
$B$ 选项：T3 对着假算红温了 1.5h 丝毫没意识到自己想复杂了，！？区区？！，所以并没有大获全胜。
$C$ 选项：同 $B$，犯下了和去年一样的错误，所以并没有一雪前耻。
$D$ 选项：你已经排除啦 $ABC$，所以容易得出 $D$ 是正确哒！另外详细证明如图：
