AI
总分100+100+100+70（种子题）+0=370，当时还不确定是否保住了最低线。看最终榜单时，金牌分数线已经涨到325了，心里一阵慌乱。对于这次比赛的题目设置，真的有很多想吐槽的地方。比如那道树的题目，放在这儿到底是为了恶心谁？出这么一个整蛊性质的题目意义何在？难道只是为了随机区分选手吗？比赛开始后，我很快解决了A题，但后来听人讨论说这题题意不太清晰，现在我已经完全记不清A题是什么内容了。接着我看了看树那道题，感觉子树upperbound的部分无论如何都像是无解的难题。看到树结构是随机生成的，我立刻想到一个复杂度为n log? n的做法：每次modify操作时暴力更新祖先节点的数据结构。然而，关于平板电视的实现细节我一直没搞清楚，虽然花了很长时间翻阅ext库，但依然找不到相关内容。这时小波直接过来尝试解答，我想大家都可能是用pbds秒过的，于是果断放弃这道题，转而研究其他题目。之后我转向贝壳那题，发现是带修区间的数颜色问题，但我不会带修莫队算法，只能放弃。随后决定回过头来写B题，在权值线段树和splay之间犹豫了一下。考虑到权值线段树的空间复杂度是n log w log n，可能会被卡住，提交后果然MLE了。午饭后重新用splay完成代码，结果只拿了20分，感觉整个局面都要崩了，于是再次去看数颜色问题。过程中瞄了一眼排行榜，发现小粉兔也陷入了困境。经过观察，我发现数颜色的数据是随机分布的，进一步分析觉得每种颜色的出现次数都很稀疏，也就是区间内满足pre(i)≥L的i数量很少，可以暴力提取出来。于是写了一个分块算法，把每块中的元素按pre排序，查询时暴力提取整块中所有≥L的数值。只要满足≥L的数量是O(1)级别，这个复杂度就是可行的。写了一会儿后通过了80%的数据，对拍时发现了不少低级错误，但最后一个测试包始终无法通过。花了整个下午调试，最后对拍也没能找出问题所在。突然意识到，我在代码中写了
AI＞0的条件，但实际输入可能包含0，而我的对拍生成器没有生成0，所以一直没能发现问题。修正后还剩三小时结束比赛，此时感觉树题彻底凉了，为了保住底线只能去试试后面的工程题。然而面对大段代码，实在提不起兴趣，索性上个厕所冷静一下，再尝试拯救C题。仔细思考后觉得，从树高很小的角度预处理答案似乎没有更好的优化方法，只能猜测树的结构很好，每次剪枝都能高效处理。于是尝试写了一个前两个操作的爆搜+剪枝方案，具体策略是维护每个子树的最大值maxv和最小值minv。当minv＞x时直接返回size，maxv≤x时直接返回0。没想到这样竟然轻松通过了第一个测试包，当时真是气得直接在赛场上骂了出来。
