GDKOI 2024 东莞市东莞中学松山湖学校
提高组 GD-0085
1.6
8:27
密码是 Qi Mo Jia you 中间有很多特殊符号。
然后环境和正式赛场是一样的。打开虚拟机以后读了一下题目，大概感觉是 T1 可以做，T2 暴力很多，T3 先放着。
选了 T1。第一想法是先随意跑一个完美匹配，然后尝试调整。考虑形如 \(u_1\to v\to u_2\) 这样的一个增广路的切片，我们的目的是使得原来 \(mch[v] = u_2\)，现在 \(mch[v] = u_1\)，对黑色边条数的影响不妨刻画成两条边的异或和。我们就是对于这样的 \(u_1, u_2\) 在一个新的图上连边 \(u_1\to u_2\)。然后我们只需要找到一个异或和为 \(+1\) 的环就可以调整了。将图改为分层图就能找出这样的环了。
9:30
一直在调 T1，程序里写的 assert 跑不过大样例。原因是这条增广路经过了重复的右部点，导致有一些改的边重复改，最后改出来不是一个匹配。然后尝试是微调一下，但是发现出现这种情况的右部点可能有多个。然后有一个美丽的想法是说一旦发现重复的右部点，就说明我们可以把中间这个环摘掉或者把两边摘掉，不影响荅案。
所以我的做法是遇到了右部点就 break 掉重新枚举起点。
10:30
过了大样例。感觉算法还挺对的。然后就去写 T2。
一个想法是离线询问，对操作从右往左考虑，每次加进来一个覆盖操作就想一下他会问么影响后面的东西。可以枚举被覆盖的每个数字，维护上一次被覆盖的时间，那么在这个时间段上的区间求和操作可能要算上这个数字，这样就是 \(O(n^2)\) 的（假装 \(n, m, q\) 同阶，好吧确实是）。
11:30
大概写完了 T2 的 60 分。然后我也忘了是什么时间反正就是写了 T3 的爆搜 10 分，做 15 分的时候看到没有什么明显的规律，也没有背 BM 板子，后悔了。回到 T2。
然后观察到一个事情，就是考虑每个数字是愚蠢的，可以使用颜色段均摊的技巧，变成一个矩形加。但是它对应的查询操作比较奇怪，是对于每一列要取其中一个区间出来求和。这个东西是难做的。一开始考虑了把所有操作记下来以后 cdq 分治，想了一下感觉很合理，写的时候突然发现复杂度是假的，查询会查到中间所有东西而且每一列的区间全都不一样；考虑了树套树，树套树的标记打不下去，怪不得做不了。
想到这些以后就急了，不写了。把提交的文件夹拉下来过了一下样例。然后发现 T2 60 分代码里面有若干地方 \(m\) 写成 \(n\) 了吓死我了。
丢失了思考的欲望。
12:30
我不想写除了考试以外的东西。
14:30
T2 不是树套树，是分块。然后分块就强行维护就行了，看着挺危险的。题解写了很多不知道在说什么东西，感觉就直接做啊。然后我不敢相信 5e5 6s 可以过根号。顺带一提我把题解 pdf 每一页的照片拍下来了，需要的可以私信我。
T3 感觉不能做。启发的东西就是前缀最大子段和的差分 \(p_i=f_i-f_{i-1}=\max(0, a_i-p_{i-1})\)。然后后面是什么东西啊。
18:00
40+60+10=110.
T1 挂了。仔细想了一下发现不能直接跳过。他不是这个道理的，可能以后找不到这个解了。那这个算法是假的啊。还是想的不够周到。然后我发现今天比赛怎么没有打过一个 python 代码的？好像不仅没拍也没写暴力。明明最后还有一小时的。这个可能是问题所在，我应该写一个状压的。T2 有 60 分感觉其实有侥幸。
我要吐槽一下，T1 有 4 个 subtasks，所以我通过了 subtask 4，在 subtask 1, 2, 3 上答案错误。