20251122 总结

一道还算简单的题。考场上很快就写出来了代码，加上调试一类的，一共花了一个小时。然后去跑大样例。重点就在这里：因为不明原因已查明是虚拟机跑太慢了，我的代码跑了 5s！！（时限 2s）。再三确认了我的时间复杂度没有问题之后，就开始了卡常。先是把线段树换成树状数组（4s），然后又把树状数组换成 ST 表（3s），进行缓存优化（2.5s），然后这时已经又过去两个小时了（我是先开完了所有题的），赶紧放弃这道题，去写其他题。最后 OJ 交上去跑了 1s，气笑了。

一定，一定，一定，不要，浪费三个小时签到。实在看它有点极限，就放心的把它交给评测机吧，毕竟评测机也是神机呢。

三个小时，我打暴力也得的分比这样高啊。

自闭了，一车人观察到了结论，就我最菜。这道题有一个不是很显然的结论：当 $n$ 较大时答案一定为 $1$ 或 $2$，我直接猜测答案一定为 $1$ 或 $2$，然后因为捆绑测试挂完了。

赛后加上暴力就 A 了，这个结论是他们打暴力打表发现的，赛后学长通过数学方法证明了结论，我是根据题意猜的。以后遇见这种猜性质题一定要打暴力检验一下！万一就差这么一点呢？！

没时间了，敲的部分分。正解不难写。都怪 T1。

时间规划，时间规划，时间规划，时间规划，时间规划，时间规划，时间规划，时间规划，时间规划。

根号平衡时间复杂度，但是数据结构学傻了。正解时间复杂度是 $O(n^\frac{1}{2})$，我整出来了一个 $O(n^\frac{2}{3}\log n)$，其实只要把树状数组换成差分，我就是 $O(n^\frac{2}{3})$ 了，对于这道题就可以过了。

学数据结构学的。暴力分。

时间规划，时间规划，时间规划，时间规划，时间规划，时间规划，时间规划，时间规划，时间规划，时间规划，时间规划，时间规划。