1. 前言
从 CSP 2022 开始（或者更早），就不太想学习算法了，即使已经知道还有好多算法没学。这一段一直在做一些杂题，比如板刷 1900，或者打比赛后看心情的补题。感觉 WC 2023 可以让我调整一下，发现自己的不足，然后加强，同时学习算法。
2. 赛前
赛前只看了一遍模板，没写。还想起来了要复习交互题，但是因为觉得考场能搞出来，就没复习。
3. 赛时
首先看题，读了好久 T1 才看懂，看起来是一个大 DS。之后看到 T2，发现很容易懂，但是越容易懂的题一般越难。最后看 T3，心里一凉，这不就是交互题吗。不过我这时还觉得交互题不会在非思路或代码上的问题耽误很久的。
顺序思考题，看到 T1，发现了很多显然的单调的性质：每行的长度递减，一行中从左到右答案递减，一列中从上到下答案递减。然后我设一行中的长度为 \(h_i\)（不是 \(l_i\) 是因为最开始读错题以为每列加格），那么一个格子 \((x,y)\) 的答案就是（设最后一个 \(h_i\) 大于等于 \(y\) 的 \(i\) 为 \(\text{find}(y)\)）：\(h_x-y+1+\text{find}(y)-x\)。这样就有了一个大暴力：枚举 \(x\)，因为是单调的所以双指针 \(y\)，计算答案的时候用二分计算 \(\text{find}\)。这样应该有前 \(5\) 个点。不过我想到 HMZ 大概已经爆切 T1 了，于是继续思考。
这时候我还是不知道 \(q|p\) 有啥用。我先想 A 性质，发现没啥用，因为既然是暴力，暴力记录一下每个操作的情况也不会寄。B 性质就更加迷惑了。这时候开始想暴力怎么写。我突然发现其实只有 \(\mathcal O(m)\) 个不同长度的段，于是这样就去掉了 \(a_{\max}\) 的限制。剩下的按照暴力跑，复杂度似乎是 \(\mathcal O(m^2 \log m)\) 的，因为常数小，也许能冲过 \(m\le 5000\)。就这样写了下去。写的过程中发现节奏慢了。调了一会就过样例 1、2 了。这时候测试样例 3，发现 \(m\) 是十位数的时候居然跑了好几秒。我突然意识到不能用双指针，因为双指针是 \(\mathcal O(m b_{\max})\) 的。现在只能换二分了，又增加了一个 \(\log\)，有点炸。改完后果然样例 3 瞬间出了。接下来测试样例 4，这个测试点是 \(m=5000\) 的，竟然也瞬间出了。但是没法检查正确性，于是我将我的答案的 -1 和正确答案的 -1 比较了一下。幸好比较了，发现在第 590 行我输出了 -1 但正确答案没有。
这时候我有点着急了，大样例怎么调啊，而且时间只有两个半小时了，剩下两道题还没思考。但是写了这么多的代码交上去错的肯定也不行，于是还是硬着头皮调了下去。这时候我还用了好多错误的方法，比如我以为 R 操作是返回某个版本（实际上是往前跳几个版本），然后看到了大样例中输出第 590 行对应的行数（好像是七百多行）往前几行，有个 R 1，就以为这是从头开始的标志。我模拟了一下到七百多行的结果，竟然恰好是我输出的结果（这绝对是巧合）。这时我开始怀疑大样例错了。模拟了半天才发现我搞错了。不过这个也让我发现了记录版本时我写挂了（但是这个有可能因为灵异原因没错）。又过了一段时间，我开始乱试。我发现 - 操作有个地方 vector 需要删除（我将所有长度为 \(0\) 的合并了，这一段代码应该没有用），有可能这里写挂了，而且我对 vector 的删除不太熟悉，于是删掉了这一段。删掉之后竟然这一个询问对了！剩下的对了一下，发现也没问题了。虽然没写 checker，但是 -1 都对上了就当做已经过大样例了吧。
（写游记的时候看了一下，不删那一段竟然也过了大样例，但是考场的时候没过啊，这可能是个谜）
这时候我看到了一个大样例有一个 \(m=40000\) 的，试了一下，竟然发现不到一秒就出了！这样是不是有可能能冲过 \(m=50000\) 啊。不过这个大样例里输出好多都是 1 开头的（相当于查询双 \(\log\)），没有啥用。
（写游记的时候看了一下输出，全都是 1，说明这个大样例没有任何参考价值）。
这时候距离考试结束还有两个小时，赶紧开了 T2。因为时间不多了，所以打算赶紧打暴力。我发现模拟退火可以，于是写了一个模拟退火。需要调一个比较好的参数，否则连大样例都过不去。我作死将时间的限制开到了 990ms。考后非常忐忑，是否这题能过该过的点，还是会 1.00s TLE。
因为调参比较浪费时间，看到 T3 的时候只有 45 分钟左右了。看到题最先想到的是枚举每个颜色，然后看它们之间的关系。不过这样想了一会想不出来。我又想到了当颜色为 \(n-1\) 时所有点的值是 \(n-1\) 的点都在 \(n-1\) 所在边的子树内，剩下都不在。那别的颜色怎么确定呢？交换这个颜色和 \(n-1\) 就好了。这样做就可以确定每个颜色所在子树了。而且我还发现了一个性质，就是一个点在的子树个数就是它到 1 的距离。这样我们就可以确定每个点的深度。按深度从小到大枚举每个点，往前找它的父亲，检验它所在的子树的颜色是否恰好包含父亲所在的子树的颜色。如果恰好包含，那么它们就是父子关系，而且它们之间的颜色就是儿子所在的子树的颜色包含的，但父亲所在的子树的颜色不包含的那个颜色。上述操作可以用 bitset 记录，做到 \(\mathcal O(\dfrac{n^3}{w} + n^2)\)，操作次数是第一个操作 \(\mathcal O(2n)\) 次（考场上傻了，其实不用交换回去的，就是 \(\mathcal O(n)\) 次），第二个操作 \(\mathcal O(n^2)\) 次，恰好可以过 \(n \le 1000\) 的点。
这时还有半个小时，而代码非常好写，于是我写完代码后还有二十多分钟。但是这个时候因为不复习交互题，就出了好多问题。第一个问题是无法编译。它总是说 vector、bitset 等不存在。但是示例代码就没问题。可能是当时太紧张了，死活发现不出问题。想了好久才发现是我没加 ::std。接下来的问题是点开 ds.exe 并输入数据后瞬间就关闭了。我没有意识到每个 exe return 0 后都会直接结束而不是请按任意键继续。到最后几分钟才发现在 grader.cpp 里加个 system("pause") 就好了。接下来告诉我 \(p_2\) 应当输出 1，我输出了 0。这时候因为时间太少了，就没有调出来问题（实际上问题是我以为最大的颜色是 \(n\) 而不是 \(n-1\)，在询问的时候出锅了）。经过魔改之后它又告诉我长度应当是 \(n-1\) 而不是 \(n-2\)。但是我看 sample.cpp 里写的就是 \(n-2\) 啊。最终还是没有调完比赛就结束了。非常遗憾。比赛后 10 分钟就调出来了。
4. 赛后
考完就去问 HMZ 怎么样。显然他不会告诉我真实成绩，但是看起来也不是很好。接下来我就抱怨 T3 的问题，说为什么出题人不告诉要用 ::std，不说 exe 会直接弹出。不过根本原因还是我对交互题不熟悉的原因。说着说着就把 T3 调出来了。
赛后的估分是 \(50+24+0=74\)，但是 T1、T2 都有很大的波动。T1 有可能能冲过一些特殊性质点（但是概率非常小，空间大概会直接爆炸），也有可能写挂了直接爆零。T2 有可能能冲过一些特殊性质点，或者过一些 \(n \le 400\) 的点，也有可能因为卡时直接全 TLE。
等出分了再说吧。
upd on 2023.1.18 晚上：分数：\(40+4+0=44\)，Cu。看到这个分数有一点惊讶。没想到 T2 模拟退火比暴力分数还少。同时得知 HMZ 分数是 \(5+76+0=81\)（详见他的游记），更惊讶了。因为他 T2 写的也是模拟退火啊！只能说我考场上实现太不精细了。照着他的代码改了一下自己的，学习到了一些有用的知识，会补到总结里。T1 \(40\) 是正常的，\(m=40000\) 的大样例能过只是因为太水了。
还有一点，T1 我的代码能优化掉两个 \(\log\)。具体的方法是，和 \(x\) 一样，\(y\) 也是一段一段的，总共只有 \(\mathcal O(m)\) 段，这样对每一段首先可以双指针预处理出 \(\text{find}\)。其次再来一次双指针就好了。这样单次查询就只需要 \(\mathcal O(m)\) 了。
心情比较沮丧，感觉这次太遗憾了。但是失败能收获很多经验，下次就能不犯错了。这次还意识到了自己水平的严重不足。赛后觉得自己如果完美发挥，也就 \(55+16+36=107\)，这个成绩和高水平选手还差很多，而且他们不挂分会更高。
希望接下来能吸取教训。春测和省选加油。
5. 总结
代码方面的：
-
没必要的东西不需要写，如果写挂了反而会浪费时间。（T1）
-
模拟退火题最好不用或少用
clock函数，太慢，换成记录次数。（T2） -
模拟退火尽量退到一个较优解后在附近只接受更优解地跳几次，或者把终止温度设为比较小（\(10^{-6}\)）。（T2）
-
如果
bitset的值域取决于输入的数，最好手写bitset。（T2） -
随机化算法不要依靠大样例，要多造数据。可以取不同的时间种子看答案是否相同。
-
少使用随机化算法。如果使用要拼一个暴力。（T2）
-
调参等玄学操作在比赛最后搞。（T2）
思路和学习方面的：
-
不要觉得多 \(\log\) 没事，常常思考减去 \(\log\)。尤其是会改变分数的。（T1）
-
熟悉新题型。（T3）
-
学习新算法，不要停留在这个水平。
-
做题提升速度，并注意细节。不要因为一个小问题调很久。
-
多打模拟赛，总结经验。不要在打模拟赛的时候觉得考试一定不会碰到这种题。每种题型或算法都要练习、学习。