SDOI2021 退役记

## 写在前面 本文同步发布在：[My blog](https://www.cnblogs.com/luckyblock/p/14645765.html)，前往阅读以获得更好的效果。 本文是在 4.11 日通过回忆构建的。因为考试日玩手机太嗨了（ 调完班上了一周 whk 之后啥也记不清了= = ## Day -1 Day -2 的时候跟着竞赛班上完了数理化生的高中课程。今天他们全都停课了，于是我来到机房划水。 先是把之前[咕了很久的题](https://www.luogu.com.cn/problem/U150047)的数据造了，写了之前一直很想写的题 [P6292 区间本质不同子串个数](https://www.cnblogs.com/luckyblock/p/14634965.html)，然后就开始上 A 岛看没有营养的媚宅文（（（ 手痒了，但并没有很好的 idea，小说写作无法 ( ´_ゝ`)旦 感觉把魔理沙塑造成纱世里那种性格可能挺有意思的，有兴趣看我开个《魔理沙的遗书》的新坑吗（  $$\text{水群水到的鲨鲨}$$ 下午 sbAliemo 和 yu__xuan 来力！久别重逢非常开心，哥几个谋划去临沂搓顿好的，群里八十年没这么热闹了。 ## Day 0 早上 8:00 准时出发。这次的道路状况很好，司机车技也很稳，简直是迄今为止最好的坐车体验。有手机真是太棒啦！！11 酒店的布局错综复杂，没有窗户光线昏暗，非常有恐怖游戏的感觉。我和涛哥的房间在最角落，一般这种死路里都会有个用来躲避的柜子之类的（（ 继续水 A 岛直到出去看考场吃饭。 从四中离开后就近来到了西边的……？不知道怎么形容的一片材料为混凝土的区域吧。 宽敞的大道两旁布满了参差不齐的饭店。但明明正值饭点，路上竟没有一个酒足饭饱的行人。空荡荡的路上只有不时扫一眼手机的黄蓝两色骑手呼啸而过。仔细看看路旁的店家，大部分都是炒饭、炸鸡、包子、肉夹馍一类，并且全都用各色图片把玻璃档得密不透风。偶然也会有几家大开城门的店，从长明着火光的漆黑中延伸出通向门外的灰色水泥地面，飘散出夹着过分的辛辣味的油烟，令人作呕。隐于暗中的男人脸上落下映着熊熊烈火的汗珠，随意堆放在门口的一袋袋半成品中闪烁出缕缕灰白头发。孩子坐在母亲身旁低矮的凳子上，盯着放光的电子屏幕，不哭，也不闹，被同样低矮的桌子上的饭盒遮住半边，看不见他的眼睛。 在这里，门头似乎只是填满“店铺照片”一栏的浪费租费的工具，桌椅的存在也只会平添清扫落灰的麻烦。我无法想象他们以什么心情日复一日年复一年地把一团团热气腾腾的“养料”埋入塑料饭盒之中，我也无法想象正小心翼翼揭开盒盖的人们正身处何方，经过了多少个小时的辛苦劳作。从前的我认为产自流水线冰冷的食物只可用于充饥果腹，现在看来，就算是温暖的饭菜，又何尝不是这般的工业产物。 我想到 Deckard 避雨充饥的小摊。百闻不如一见，习惯了家乡悠闲的生活节奏，看到这样的景象，我未免有些恍惚和晕眩。 我不知道该以什么样的心情面对这一切。遗忘是一记猛药，以前的我肯定会掏出手机刷刷 qq 看看 b 站，并在离开这里后就忘记所有。 “我们也会像这般活着吗？我们为什么要像这般活着？” 这片景象同这个问题一起萦绕在心头，久久不散。 --- 扯远了，吃完饭之后哥四个去银座逛了逛。 星期五下午 13:00， 身穿校服， 带着手机， 无目的地乱逛…… 草这不是街头混混这是什么，笑死了。 门口测体温的大爷看的眼神都不一般。 这片简直繁华到爆了，有这么好的地方不去去偏僻楼盘恰饭的我们简直是憨批。哥四个相约晚上来搓顿好的。 下午回去继续颓颓颓，写了个 LCT 维护 parent 树被卡常了草，这棵树直到今天晚上都没调出来。 晚上去吃了麻辣烫，出发试机。抽签的时候遇到 Pbri 了，他居然还记得拉比这张脸，拉比真是太感动了。 抽到的位置比较清闲，座位右边是备用机，进去的早左边还空着。正当我用快读和 scanf 拍 a+b 的时候左边坐过来一个人，当时也没注意。瞟一眼发现这个人居然把掌心缩到袖子里，当时还觉得这人好柔弱。后来一想不对啊怎么会有♂做出这种行为呢！111 不知道为什么突然变得很慌。 试完机回去继续颓颓颓，晚上居然没收设备草，于是开心地水到 23:30。 ## Day 1 考场外面的厕所是什么牛逼地方，巨型大窗户，比机房都亮堂。对面就是女生宿舍，无法理解设计师有过多么悲惨的人生经历。 开局看 A。一开始没看到 $m$ 的限制，先考虑了二分答案。一想这不是傻逼题吗（（（ 又读了一遍才发现不对劲。觉得 1e6 CCF 的少爷机肯定能跑过去，于是考虑先排序再暴力枚举构成极差的较大数，再二分极差的大小。问题就变为需要经过翻面，使得它们的权值在要求的区间内的牌数是否不大于 $m$。考虑预处理排序后牌正面的数的前后缀最大值，最小值，个数，特判一下较大数位于反面的情况就完事了。手生了调了 2h 才过大样例，极限数据在考场的 8100 上跑了 1.1s，问题不大。 之后看 B。构造？？？我先放个*在这里，爆搜跑路了。 之后看 C，理解成每次删除边都是独立的了，手玩 1h 样例没玩懂，跑路了。 估分 100 + 30 + 0，标准退役分。 临沂一中还管饭的，比隔壁 SNOI 好多了（不是 下午回去继续颓颓颓，企图在某本子网站找 ke-ta 本看，但是被垃圾网打败了，早睡了。 ## Day 2 开场看 A，想到一个非常牛逼的做法。首先按照询问序列冲重编号各点，考虑建立两张重构图，令每个点连向其编号 $+ 1$ 的点，一张图自底向顶连，一张图自顶向底连。由于序列中每个数不重复出现，重构图一定是一棵树。将询问的路径拆成自底向顶连和自顶向底的两段，预处理自底向顶的树的倍增数组，得到到达第一段顶部时匹配的位置。再考虑用 LCT 维护一下后一段就完事了。复杂度俩 $\log$。 发现不会写，而且常数飞天，睡觉了！ B 直接超爆搜，滚蛋了。 C 看着像传递闭包，如果我会 $O(n^2)$ 求，我将加冕为王，但是并不会，滚蛋了。 估分 40 + 30 + 30，标准退役分。 ## 后日谈 好聚好散。 别了。