「By the love for the OI, and the world.」

· · 生活·游记

参赛之前

周五那天把省选计划后期（2023.2~2023.3）的最后一道 AC 率达到 20\% 的题补完了。

正好三年过去了，我到底学会了什么呢？

是学会了盘狼人杀的逻辑，还是积累了犇犇魔怔语录，还是发现了自己文化课垃圾一样的成绩，还是意识到自己在和人交往的过程中纯属人机不会和正常人说话？

三年（半）前，我在 CSP-S 中作为 240 分的选手几乎引领整张榜单，然后觉得自己很年轻，很厉害，很有实力。然后开始摆烂，每天和那些课内学的和明镜一样的数竞学生去摸鱼？

正确的，我仿佛有看到了电脑前那个为了输出蛇形矩阵调了一个又一个小时的五年级小学生，那个因为 using namespace std; 没写问了一次又一次老师的小学生，那个因为在入门语法培训机构的模拟赛拿了第二而开心了好几天的小学生。

现在呢？我还愿意为一道题专心致志地调三个小时吗？我还能去深究一个算法吗？我还能重新感受切题的乐趣吗？

我总是以为自己很年轻，很有机会，未来还有很远的路。到头来，没想到终结来的如此之早。

就在明天吗？

明天，是 2023 年的愚人节吗？

明天，是 CSP-S 2022 要出成绩了吗？

明天，是第一天来算法俱乐部报到吗？

并不是的，明天（或许）是这一段区间的右端点。

我只复习了 manacher 算法，或许在现在的某个时刻，和若干年之前的某个时刻是完全等价的。一切是对称的吗？

我们总是以为别人的成功是碰巧，自己的成功是实力，认为只要有了所谓的“鸿运”就能获得想要的成功。可是真的如此吗？

一试

进校门前放了一遍秋殇别恋。

下载压缩包好慢啊。

不过密码不难输。

T1 感觉像是很牛的题，但考虑到只有 10 个测试点估计是人均的签到，做！

想了一个自以为是的二分，写！

等等，我好像不知道序列的长度，意味着我不知道中位数的排名范围，那我玩啥。但感觉可以二分，这玩意应该是一段区间。

是吗？考虑左右两边有一个个数范围很广的数，中间一段区间的数都有可能是中位数，这段区间里可能有很多可以分布的元素。他们甚至不一定连续。

那如果是某个区间和这些元素范围取交集呢？好难写。那可不可以让他们连续呢？离散化也不想写。硬着头皮推式子，写！

排名怎么假了？哦原来如果一个数出现次数足够多那么一定可以是中位数，那必须考虑到中位数本身大量在序列中被放入的情况，那不如刻画大于小于（等于）目前要二分的中位数的四种情况的个数的大小关系？式子推完了，将信将疑写了一下，不断地根据小数据改来改去，不得不说样例很良心，最后确认了式子对了，过了所有大样例。

一个半小时了！甚至还用了几分钟纠结该不该急一些，决定还是先看看后两道试题再想 T2。

T3 瞅到之后不想看，T2 看完之后不想做，决定先开 T2，然后开始想有向图怎么处理，想当然的想了个很简洁的分块，按照 a_i 重编号，维护 b_i 然后对于询问，边角直接处理，中间每次修改记录段 b_i 最大值，结果发现这个无法和 bitset 结合。写了个 20 分暴力发现只能跑路了。想过很多种思路，首先排除了在线做法，因为 DAG 可达性结合什么东西都很困难，然后考虑到把询问挂到结点上、左端点上，莫队感觉没前途就跳了。

T3 一眼 8 分纯暴力，转化下题意就是不存在图上两条边画在排列上在非端点处相交，感觉很困难，链的部分分想假了，没想到把 1 放在前头，最后没时间写树的部分分了。

估： 100+20+8 。

面到了 xhabc。

二试

进校门前还在循环秋殇别恋。

下载完压缩包很早，毕竟压缩包不大，看 years 数据包很小，感觉像是大模拟状物（儒略日？），move 数据包很大，像是大数据结构？很想要大模拟，因为想靠着大模拟死磕翻盘，豪赌111

move-years-seal，推箱子不是我们计 * 客基础算法学期压轴题嘛，哦哦看起来一维数轴问题，之前打北京营的时候对一维数轴问题 ptsd 了，T2 怎么又给我来 15 个点的神奇计数，T3 怎么是神秘题。决定根据“不开 T1 你打个什么”的原则先看推箱子。

然后发现可不可以根据特殊性质的箱子不交来贪心依次移动 ddl 靠前到靠后的，感觉有前途， a_i \le b_i 的话会推着前面的箱子向前走，感觉也可以贪，好像箱子避让一定不劣？

想了一下需要区间覆盖区间按值分裂区间求和，用了下位置减去下标去除严格偏序要求的 trick。要不然避让的时候目测很难写。然后直接开干线段树，平衡树怕写挂。线段树上二分虽然没咋复习但毕竟很基础，区间覆盖和求和更是基础懒标记用法。哎我怎么小样例一次过了，哎我怎么大样例挂了，哦哦挂在小数据上，好好好，哦我没有给结点信息完整赋值，用了构造函数赋值线段树结点信息但是为了省事用了函数默认值，结果给 node 传 int 进去不报错也是神人了。哎我怎么大样例又挂了，哦我修改时没 pushdown，Yes/No 的题测样例还得小心点，哎我怎么超大数据挂了，哦我判断是否已经到达目标地点用的是初始位置而不是当前位置。过（题），交（代码），翻（第二题）。哎我程序回收系统怎么似了，重启！

T2 感觉有向图外向最小生成树不好做，然后 w_i=1 似乎可能可以试试？ w_i 互异有啥用啊。等等， w_i 互异可以使得生成树的边集唯一确定！直接开算（笑点解析：写这个时间比纯爆搜短）。然后考虑怎么写 w_i=1 ，维护连通性不太好弄，考虑状压 DP 维护哪些结点在外向生成树上？但是似乎还要维护哪些点是上一层的点，按照层次去加点，要不然似乎会算重？跳。

T3 感觉很牛，没啥时间了写完暴力跑路。

估： 100+24+8=132 。

最后在 T3 的代码底下注释了这么几行：

//By the love for OI, and the love for world.
//Sayounara(maybe, but I don't want.), OI!

以此，献给这条人迹罕至的路上，五年的岁月。