首先很荣幸能够作为中国队一员参加在日本筑波举办的第 30 届国际信息学奥林匹克竞赛，感谢 CCF 和科协的组织，感谢领队老师们带队和翻译题面的工作和对我们的鼓励，感谢我的教练叶国平对我的一直以来的关心和指导，感谢国家集训队教练张瑞喆在 IOI 赛制上做的努力，也感谢主办方对比赛的重视与支持。

因为今年的集训大多为集训队员开放了 IOI 赛制，同时在赛前也参与了一段时间针对性的模拟赛，因此对赛制还是比较熟悉的，加上日本和中国的时差只有一小时，可以说相当于半个主场了。来的时候碰到了叙利亚等国的友人，我们四人也在机场前合影留念。

和往年一样，每支队伍都有一名 team leader，据说他们都是筑波大学的学生/留学生。我们的向导是一位姓路的中国留学生，也要感谢他给我们提供的许多帮助。看起来有很多中国留学生报名了志愿者，四处都是和我们打招呼的中国人，似乎就算英语交流起来有困难也不成问题。

虽然前两天的时候由于饮食习惯不同(冷食还是有点难受)，大家都不太适应，不过主办方及时发现，后面几天还是很开心的，这个要点赞。

在日本印象比较深刻的就是当地人的综合素质，例如道路上虽然没有垃圾桶但是还是很整洁，在电梯上会自发排成一列留出应急通道。感觉国内还是有很多可以学习的地方。

这次 IOI 的赞助商较多，第一天的 excursion 基本上就是参观一些赞助商的地方。很多地方都只有日文，很多国家的选手都觉得非常无趣。第二天要有趣一些，但或许是因为场地离住宿点较远，主办方又安排了连续 3 个场馆的参观，因此每个地方的参观时间都较为短暂，甚至在一个国家公园中只是沿着外围绕了一圈都有些赶，感觉时间如果充沛一点会更开心。

最后一天跟着 guide 去了一家日本料理店，也算是在一定程度上体验当地的生活吧。

和加拿大队、澳大利亚队、美国队(主要是去见Benjamin Qi)、日本队、香港队、澳门队选手进行了一些交流。加拿大队和澳大利亚队都有会说中文的选手，交流起来比较容易。

回到比赛本身。练习赛在 IOI 开始前的几周就已经挂了出来，但做的时候还是出现了一点小差错找了很久，不过结束之前总算还是写完了。今年的评测系统新增了可以看每题所有人得分占所有人总分的比例的功能，感觉看起来还比较靠谱

虽然第一个考试日前有早睡，但还是早上三点五十就醒了，感觉还是很紧张的。guide 和许多其它领队都给我们加油鼓励，感觉就像是主场一样。

主办方在我们到达场馆时似乎并没有准备好，于是先让我们坐在车上，一会之后才慢慢开始入场检查。虽然我们队是很早进场的，但也已经 8:50 了。不出所料，比赛推迟到了 9:40 开始。比赛快要开始的预告得到了全场热烈的掌声。

看了看文件袋，并没有发现里面是有纸质中文题面和草稿纸的，于是拿英文题面充当草稿纸使用。下载了 PDF 题面，先读第一题。读完后觉得第一题可能是个简单题，但想起之前发生过的在一题上吊死的事情，还是去阅读了第二题和第三题的题面。第二题的数据范围是 Q ≤ 50000, H × W ≤ 106 ，看起来就是个分块好题。第三题读完题觉得是和互测的最小方差生成树一模一样的板子题，外国选手估计不太会做，但是这题写起来很花时间，于是决定先放一放。

想了想第一题：操作次数在 N 左右，看起来就是个逐位确定。似乎询问第一个字符只要 3 次，最后一个字符要 2 次，中间的每个只要 2 次：询问 SaSbaSbbSbc 即可，于是这样就是 N + 3 次解决了这个问题。想到这的时候附近的人都还没有敲键盘，感觉就很有信心。

在 21 分钟的时候写完提交，得到了 5 分的好成绩，随便手输了几组都是对的，感觉情况有点不妙，跑去写对拍。给 N 确定范围发现了还有 N=1 这种事，改了改得了 97 分。不过似乎中间的部分可以各种瞎卡常数，但想到 N=2 才发现根本不会做。

对着代码看了 5 分钟发现还有个东西叫二分，改了改就过了，这时候还有四个半小时，交完后评测系统 CMS 突然挂了。还好这时候还不用交题，于是接着去看题。

对着第二题和第三题不知所措，写了个第二题的暴力，感觉应该先把这个题放放再说，打算提交的时候发现 CMS 还是挂的，先去想了想第三题暴力怎么写。过一会 CMS 修复了，得到了和期望一样的成绩。于是开始写自己想的第三题暴力：每次把两端点都 ≤ R 或 ≥ L 的边加进集合，判断 S 和 T 是否联通。

写完发现根本过不了样例，画了画图才意识到想错了，还好之前训练的时候这样挂过几次，没冲上去就直接写最小方差生成树，不然咋死的都不知道。于是回去改第二题的 O(Q (HW)0.5 poly(log(HW))) 做法。中途终于意识到第三题暴力咋写了，于是在 106 分钟改对了暴力，然后又回去继续写第二题。写了一会感觉这个复杂度也不是个事，思考了一会有没有更优的做法。这时候看了看得分率，感觉第三题的得分率好像不太对，于是又回来想第三题。

编了好几个错误的做法之后终于转化出了一个比较可做的题意，对着问题看了十分钟才意识到是一个简单的二维数点，于是在 172 分钟通过了该题。

这个时候可能还剩两个多小时，因为前面分块改了一半，感觉很有信心搞出一个能跑过 H = 1 ，还能在 H ≠ 1 上一战的分块算法，然后就一边改一边交，改一点交一点。

改了一个半小时发现情况有点不对，因为之前写的时候没有注意空间限制，我本来想改的分块似乎不是 268MB 内存可以解决的。想了想怎么压空间才发现时间已经不早了，于是赶紧放弃手上这份代码去写部分分。想了想几个部分分好像除了 H = 1 都挺容易，于是花了十几分钟过了，然后开始对着原来的分块改 H = 1。

到最后十分钟的时候改代码的手都是抖的，感觉也不够冷静了，最后枚举一个不太想的清楚的地方爆了几发都没过，很后悔没有一开始就奔着 H = 1 的部分分写。

考出来感觉只有 237 分，应该不算什么好成绩。我们四个选手在场内交流了一下，发现 237 甚至是中国选手最高分，感觉也就只能在金牌线左右摇摆了。结果出来后发现除了 Benjamin Qi 之外没有选手超过 237 分，但是第一天输了这 63 分感觉不太追的回来了。

第一天的得分率非常稳定地体现了难易的情况，做起来比较舒服。

第二个考试日的早上发生了 6 级左右的地震，不过我不知道为什么睡得很熟没什么感觉。这一天的比赛开始时间又推迟了十分钟。

发现信封中原来还装了中文纸质题面喜出望外。由于第一题题面很长先跳过，读了第二题和第三题都感觉看起来挺可做的，尤其是第二题还是我比较擅长的一类交互题，而且可能是个 Hard ，估计应该不会考得太差。

草草阅读了第一题的题面，开场便发现第三题的得分率飞快地达到了 100% ，随后得分率一直稳定在 90% 左右，估计第三题是个较为简单的试题。对着题目想了想感觉 60 分的暴力还是可以强行写出来的，思考了一会无果之后决定先去做第二题。因为第一题看起来就像个中档题，第二题可能是这一天最难的试题，因此打算先过为敬。

第二题是个非常有趣的题。前四个子任务都是一棵树，想一个做法应该没有任何难度。第五个子任务应当是对做法有提示作用的，因为这一组数据的限制只有 a = 1, b = 2 。稍微想了一下发现只要支持给一个点集 V 并查询 S 和 T 在 V 中的状态是否相同即可解决这一问题：首先用 log n 次询问将点集区分为两个集合，并分别二分，这样就可以解决这个问题了，由于一开始要一次询问可能会爆掉 50 次询问的限制，但这样微小的常数是可以优化的，一看就非常符合出题人的心理。如果我们将 V 和除 V 以外的边的代价设为 B ，其他的边设为 A ，那么我们要得到的只不过是经过 B 边次数的奇偶性。于是我很快讨论出了当 a = 2p × r, b = 2q × t, p ≠ q 时的解法，并开始思考 p = q 时的解决方案。想了一段时间无果之后先行提交了之前的代码，果然只通过第五个子任务，这时时间已经过去了 84 分钟。

继续想了会，因为第三题的得分率居高不下又去想了想第三题，结果快两个小时的时候还只有一个子任务的分。还有个第一题没太读懂感觉这样容易出事，于是回去仔细读了一下第一题，看了看数据范围怎么感觉随手写个线段树就有 61 分。过了一会发现可以并在一起建一棵大线段树，这样就达到了题目限定的 N + log2 N 次操作的限制。感觉这个题目比后面两个题简单多了但是得分率甚至只是和第二题差不多，看来这个得分率也不太靠谱。

断断续续写了半个多小时，还拍了拍才在 157 分钟解决这个问题，看了看得分率情况仍然是第三题居高不下，但第二题的部分分还没有拿完，于是回头去做第二题。对着部分分看了几分钟发现 18 分的代码加一行就能得到 69 分了。因为感觉金牌比较稳了，这时第三题的得分率也终于被第一题反超，于是尝试了一些乱搞来修之前的做法，结果甚至没有多通过一个测试点。于是继续去想第三题了。

对着题目想了半个多小时还是不太会，于是先写了个暴力，然后想想 hi ≤ 20 有没有什么能写的做法。hi ≤ 20 可以理解为笛卡尔树不高，想到这里突然发现这题可做多了。考虑一个询问 [l, r] 时，我们只要考虑其最大值的位置 x ，并枚举开会位置在 x 的左侧还是右侧，于是问题转化为对每个笛卡尔树上的区间维护前缀和后缀的所有答案。

想到这突然感觉这是个水题，直接建笛卡尔树写了个暴力，虽然感觉写的复杂度不对不过莫名其妙就得了 60 分。时间还剩下 40 分钟，于是考虑用线段树维护这样的前缀和后缀的答案。感觉转移是单调的，也没多想就开始写了。还剩 25 分钟时似乎改对了数据结构以外的部分，打算继续写的时候突然感觉有点不对劲，因为这样二分就像是对着这个题一开始就直接二分 x 的位置一样，于是又凭借直觉认为这肯定是错的。

感觉已经不能冷静思考了，想了想也没啥好办法，时间也不剩多少了就打算 rush 一个李超树来维护，说不定写完交上去过了还能翻。不过显然奇迹没有出现，最后十分钟的我已经完全失去了冷静，最终写出的代码连样例都没有通过，虽然赛后改过了样例但感觉两个 log 也没有什么回天之力了。

队长第二天翻盘了，但R爷第二天有点崩，感觉金牌不是很稳。直到出来之后，guide 和一些其他国家的领队祝贺中国队四金，才放下心来。但打开排行榜，发现和第一名 Benjamin Qi 只差了 33 分，队长和他只差了 30 分，感觉还是有点难受。虽然按照实力来说确实是不如的，但是面对一个第二天没有发挥好的对手，还是因为自己的几次失误输给了对方。如果 Day 1 不要想那么多，至少 H = 1 是可以稳稳通过的，而差距也仅仅只有这一档 33 分；如果 Day 2 少在 T2 上花一点时间，或哪怕是在最后仔细想想之前二分的想法是否正确，坚持写下去，这 40 分也许就不会丢。虽然心里还有些不甘，但结束的便已结束，向 Benjamin Qi 表示祝贺。

综合来看本次 IOI，我能够以并不突出的能力，取得 rank 3 这样的成绩，得益于在这样的大考考场上的冷静，这与有过的几十场 IOI 赛制训练赛是分不开的。但我没有取得更好的成绩，也应归咎于在考场上的不够冷静。当面对重要比赛时，训练有素的选手应当具有一颗大心脏，在分析得失上要理性，不能纠缠于同一题，也不能纠缠在自己擅长的提醒，面对并不充沛的时间时也一定不能心急。只有一直摆正心态，才能在这样的赛场上发挥出自己应有的水平。

这次 IOI 中国队取得 4 金的成绩，选手分列 2, 3, 6, 23 名，算是历年来较好的成绩。今年的试题和 16 年及以前的试题较为类似，每天都有一道相对简单的试题，同时在一试有一道中国选手较为擅长的数据结构题，二试也并没有拉开较大的分差，对中国队的选手较为有利。今年 IOI 中新提供了可以查看每题总得分与所有题目总得分的比值，在一定程度上有利于选手发挥出自己的水平。但在二试中，我们也看到了这一比值往往会受到部分分的影响，不能真实反映这一题的难易程度，这一点尤其要注意。同时，IOI 中许多部分分对较难的正解会产生提示作用，但也会产生一定误导。因此在比赛时要根据情况及时调整策略，较难的题不要死磕，多得一分是一分。