APIO2026 打铜记（rk3 也是铜）

· · 生活·游记

9:10 开题，都看了一遍，T1 是传统看上去不难计数，T3 是传统 cnoi，T2 懒得看。

然后十分钟内开写 T1。写了一半发现状态第三维根本没编。要了张草稿纸，画了五分钟就画明白了。在 9:49 轻松通过。

然后想了会儿 T3，发现 AB 性质好像本质简单，想了想才发现 n\le 10^3，q\le 5\cdot 10^5 是 O(nq)。发现好像不太可做，去做 T2 了。

T2 先看了部分分。第二个包做法是 a=[4,6]，直接比 a_0+a_1 和 a_2。所以毫无启发性。

花了 0 秒猜出第三个包的 a=[1,2,4,\dots]，编了一会儿，在 10:18 获得了 45。然后改了改二分的常数把第四个包弄到了 10 次，10:28 获得了 67 分。

然后算了一下 3^7 就比 2000 大一点点，吓哭了。那目标就是对着三分编了。想了好久前缀比后缀，发现不太对。后来随机思考了一会儿发现可以前缀加后缀。我去不早说。纸上手玩了一会儿 w=9 发现三分是对的。然后怎么一直三分下去呢？好像直接 a=[1\dots w] 是不是做完了。写一下，11:04 获得 100+100+0。怎么两个小时不到就金牌了？

然后 T3 先想了一会儿确定 68 应该不是很难，但是拼起来很难，虽然 68 不一定要都拼但是 40 可以先写，11:29 通过了。

然后忍不住拼了一下链和 d\ge n/2。链的做法是处理一下每个线段端点的下一次移动，直接倍增一下做完了。B 的做法是只会往直径中点跳，然后相当于给定序列 a,b，每次求区间 [l,r] 内 a_i\neq x 的 b_i 最值。st 表维护一下两种 a_i 的最小值即可。两个分别拍了拍，12:19 通过了 56。

然后去上了个厕所，想到 C 可以加个分块变成小于 n^2。然后莫名其妙只想 C 不想正解了。编了好久 C 怎么写，发现要支持维护一个点集，找最远点。完全不想写点分治，于是愣了好久没写代码。最后发现这个集合一定是连通的，然后从整图一直收缩直到单点所以次数是对的。但是我没发现多想想就是正解了。后来决定写线段树维护直径端点，气笑了。在 13:29 艰难调出来 O(n\sqrt q\log n) 显然没有获得分数。调的很慢，写了一堆错，但是心态很不错，256 应当不低（其实是最后的第五名）。然后最后发现可以改成 C 但是要多建图写一坨倍增。13:53 艰难改出来了。100+100+68=268。最后代码 9kb。

看了一下发现大概率是 300- 最高分，那稳了。出来问问感受了一下应该没什么 ak。再一问一堆人不会 T1。我请问了？？？？？？？？？？？？？？？？如此弱智题？？？？？？？？？？？？？？？

复盘一下感觉不对着暴力打很大概率能直接做出来 T3。要是交换一下后两题说不定 ak 了。生气了。

最后结果是第三名。哦耶。