GDOI2025游寄

· · 生活·游记

Day -14

开始集训。

Day -13

洛谷的省选加油赛掉等级分了。www。

Day -7

月赛直接 Div.1 Rank 30 / Div.2 Rank 15，等级分终于上 2000

Day -1

中午发车，去南海实验。摸 Fish 了一下午。

晚上尽管提早听一些治愈系音乐，但是习惯性失眠。。。

还有好果糖聚聚的直播续命。卡哇伊，没到下播我就有困意了。

Day 1

提早一节课到考场。

开题！

T1 一看就懵逼。观察到要求的是数量，于是类似于离散化的思想，对每一段的 x 统计个数，再统计小于、大于这个值的个数。随手推个式子，大样例过。（25 min）

T2 更懵逼。不过很快发现可以强行上树套树。发现不好维护每个点可到达的点。突发奇想可以使用 dfs 序，这样每个点可到达的点所组成的区间较小。对每个数，以 a[x] 为第一关键字，dfn[x] 为第二关键字存到树套树里。强行修改。不过不会证明/证伪，过多少只能看脸…… byd 树套树写了我 2h。调完考试只剩下 30 min了。

T3 看完打了个暴力分结束。最后一分钟记起来要写个人信息文档，光速写完。。。还好手速够快，要不然就炸了。

预估：100+[20,60]+8=[128,168]

小插曲：一开始我室友的家长跟我说要一起出去吃晚饭。结果 18:50 还没动静我就点外卖了。。。2 分钟后他就喊我出去吃。我只能婉拒。尬尬尬尬尬尬尬。两个极度社恐+I人是这样的。房间安静的不得了。

小插曲2：点个外卖，到了以后，我下去酒店大堂拿。结果服务员说机器人给我送上来房间了。火急火燎回房间。我正要领取，机器人说“已超时，正在返回”。。。又陪着人工智障从 19 楼回到酒店大堂。找工作人员输入密码把它暂停了才拿到。破事真多。

Day 2

6:30 自然醒。都是 whk 把我调教的。

上考场，开题！

T1 显然要按时间排序。从小往大处理。假设正在处理 i 号。假定它当前的位置在目标位置的左侧。那么它就会向右推。设 pos_j 为此刻 j 的位置。对于右侧的某个 j ，如果 b_i+(j-i)>pos_j 就需要付出 (b_i-i)-(pos_j-j)。突然发现所有满足上述条件的 j 在调整完后 pos_j-j 的值都相等。自然地想到线段树维护 pos_j-j 这个值。操作就变成区间求和、区间覆盖、单点查询（更新正在操作的 i 的 pos_i 的值）。还得有查询最左侧大于某个数的位置和最右侧小于某个数的位置。记录下区间最值就行。（1h）

然后，就没有然后了。后两题写完暴力就罚坐。

预估：100+12+8=120

预估总分：[128+168]+120=[248,288]