记游 5202 选省合联

· · 生活·游记

省流：100+20+8+[72,100]+24+8=[232,260]。又要五倍队了 /kx。

前情提要：关于我在 NOIP 考场上写假的整体二分而不是 traverse 的指数级容斥最后还倒挂 12 分喜提五倍队线这档事

Day -1

非常好信心赛 from BSZX，使我不会 deque 维护需要翻转的凸包。根本注意不到只需要把多余的部分弹掉然后全局翻转，只会暴力平衡树。

下午不补题了，摆摆摆。

Day 0

摆了一整天喵！

下午查询初中同学的机位以试图面积，结果他们还没发准考证？？？多少有点神秘的。

Day 1

到达成都历史最高城——石室中学！哟这不是正在拍合照的 JXFLS 吗？还是看看远处的校门吧！

寻找初中同学未遂，就跟在 JXFLS 大部队后面进校了。

进场进的比较早，遂写缺省源。写完写歌词。本来想写《明明明月是前身》的开头跟结尾的，但是发现开头结尾加起来有 4 句话，而题只有 3 道！于是在 T2 和 T3 写了开头，T1 用原词（《临江仙·明月寺前明月夜》）替代。

开场！noi-2025-!!!

欸这个 T2 怎么 6S 2G 啊，欸这怎么是巨大 DAG 上数据结构啊，算了还是先看 T1 吧。欸这个 T1 怎么这么神秘莫测，仔细想一下，所谓中位数就是前面和后面的数量相等。我们直接枚举每一个数，区间会被分为三类！先最小化前后区间的差，只要中间区间总数大于这个差即可！离散化一下就做完了！

我写写写，欸我怎么过不了小样例？哦哦差的正负是有影响的。怎么还过不了？哦哦离散化错了。怎么过不了大样例？哦哦离散化又错了。怎么还过不了？哦哦离散化错第三次了。怎么还过不了？哦哦原来幸运数字必须是出现过的数。哦哦过了，但是怎么花了 1h+ 才过 D1T1？不牛逼。

开 T2！这个可达性很难受啊。先把所有点换成以 a_i 为下标，这样查询是 RMQ，两种修改的区别似乎不大？TL = 6S 就先不想 \text{polylog} 了，考虑定期重构，假设我会快速处理可达性，那么在查询的时候把累积的修改做一遍就可以了，这个是简单的（吗？）。为了做到这个，我可能得用线段树合并之类的处理可达性！先写一下！

我写写写，写了鬼知道多久，欸样例 3 怎么根本跑不出来？欸我是不是又编了个假做法？冷静一下，如果我每次查询是 u\ a_v\ a_v，那是不是就能判断 u 是否能到 v？那这个是不是 DAG 上传递闭包？那是不是不能低于 O(\frac{n^2}{\omega})？我草原来我之前一直在挑战图灵奖！

好的，上个厕所冷静一下，回来先把 T2 的 20 分写了，然后看一眼 T3。哎这个题意怎么这么神秘。花了不知道多少分钟想象了一下 T3 在干什么，然后发现只会爆搜！哎不管了，8 分也是分，先写了再说。欸写完怎么 12 点了？我后两个题还没有一点头猪呢。再想想 T2，现在已经知道只能 bitset 求可达性了，现在我有每个点的 bitset，如何 RMQ，如何修改？哎再等等，bitset 一遍是 O(\frac{n^2}{\omega})，我要是定期重构是不是直接就跑不动了？那我不会了啊，看 T3。哎 T3 怎么还是只会爆搜？哎怎么只剩十多分钟了？算了，开摆！100+20+8 离场。

出来先问了一下同考场的 @Mini_PEKKA 和 @Fasterfaster。pekka 和我一个分，但是 快快 有 160 pts，非常牛逼！

然后在出校门的路上遇到了 @NATO。伟大的 那头 使用神秘分块 + 二分场切了 T2，但是没时间写 T3，获得 200 pts，感觉是要进队了。

出校门遇到了以前的学长 @Fated_shadow，然后就被初中同学大部队逮捕了，然后就被拖去吃了个午饭。午饭巨大辣，所以事实上我的主食是士力架。午饭过程中发现他们也基本都是 128 pts，属实绷不住了。

下午找 那头 问了一下 T2 的做法，感觉至少 那头 的 O(\frac{n^2\log n}{\omega}) 是简单的啊，为什么我不会呢？那既然事已至此，先开摆吧！

于是摆到了晚上 11 点然后睡觉。

Day 2

进场！写缺省源！写歌词！其中 T2 和 T3 用的《明明明月是前身》的结尾，T1 是间奏时的那首诗。

密码是 helloworld。不是怎么这么奶龙啊，不能换个 D1 那种有气势点的？

先扫了一眼题，一个 10^9+7，一个 998244353，感觉很不妙，都不像是我能拿什么高分的题。所以就先对着 T1 创了。

考虑 A 性质，哦哦只需要把所有区间长度加起来就行。考虑 B 性质，显然按 t 排序依次推。考虑 C 性质，哎不是你这个 C 性质有任何意义吗？正解不就是两遍 C 吗？那考虑正解，按 t 排序应该还是对的，只需要能快速处理受到波及的其它箱子即可。那维护每个位置对应的箱子编号听上去就不好做，但是注意到整个过程中所有箱子的相对位置不变，所以只需要维护 0/1，找第 k 个箱子就是找第 k 个 1。那考虑找到被波及的箱子会被推到哪里，就是二分第若干个 0 在哪里。推完之后箱子显然构成连续段，所以使用区间赋值即可修改。然后算答案，这个可以拆成操作前后 1 的下标和之差。使用动态开点线段树维护，是不是做完了！

我写写写，怎么疯狂 RE？哦哦有 corner。欸怎么大样例不对？哦哦二分爆炸了。欸怎么最后一个样例 RE？哦哦数组开小了。欸怎么最后一个样例第 4 组 WA 了？这又任何道理吗？丰矿的调试，调调调，调到了 11 点，我去怎么是线段树二分的某两个变量名写反了？这下过了（真的吗？）。但是花费了 2.5h 在 T1 上，还是太不牛了。

火速开 T2，好的爆搜有 12 pts。B 性质是在干嘛，生成树唯一？好的相当于求一棵固定的树出现的方案数。考虑枚举可以作为外向树的根的点集 S，其构成的虚树必须是双向边，剩余边至少出现向外的那一条。然后以 (-1)^{|S|+1} 为系数容斥就可以了。好的现在我会 24 pts，先写之。

哎我草这个爆搜怎么这么难写。怎么我写完 24 pts 已经十二点半了。赶紧冲 T3。随便写一个 O(\text{不知道}) 的爆搜，能过 8 pts。这个时候又只剩十几分钟了。再回去测一下 T1 的样例。嗯，很好，最大的一个跑 0.6s……？我草这个样例怎么只有一组是满的啊？？？那不是实际运行时间要乘以 6？那我这过个锤子啊？？？我卡卡卡，卡掉了两次线段树操作，成功卡到 0.5s。哎但是只剩两分钟了，没时间了啊，卡不过去啊。

喜提 [72,100]+24+8 离场。具体多少坐看评测姬心情。帮帮我，评测姬姐姐。

出场发现怎么大家都比我高，哦哦 那头 比我低，但是他 D1 200 pts 已经不太能出队了啊。

中午和机房同学聚餐。聚餐玩回家摆烂。在此控诉奶龙 CDQZ 打完省选不给放假还要去值周。