3/11 考试总结

时间安排

7:30–7:50 读题，T1 是个利用随机性的题目，T2 dp,T3 不知道是啥。
7:50–8:30 T1,对于随机有个结论时最值突变不超过 log ，于是可以处理出所有 log 个区间然后统计答案，但这暴力做是个 3log 铁定过不去。
8:30–8:50 T2,对于部分分可以无脑容斥，以及状压 dp 什么的。
8:50–10:30 T1,写完暴力然后码。有 3log ，然后用线段树二分之类的可以去一个 3log ，再加上分讨就是 2log ，然后测大样例跑了 1s 多，自己随机造个数据要跑 10s 。卡卡常仍旧是过不去。
10:30–11:50 卡了卡T1，写T2部分分。

回顾反思

T1：
用到随机性质，我知道最值突变只有 log 次，但是不知道对应区间长度也是 log 次，于是直接暴力，稍微减减肢就是对的。
赛后问了问同学怎么观察出来的， wxq 说打表打出来的，而且他说他用正确性换时间，写的没有正确性但是随机就是能过。
这个结论积累一下。一个证明是，考虑笛卡尔树，随机时树高 log ，于是每个点贡献和累加再均摊，每个点子树大小平均就是 log 。
还是要学会多打打表，尤其时这种涉及一定随机乱搞性质的题目。
本场比赛在这道题上实在时太莽撞了，一直急着考虑能不能把 2log 卡进时限。几乎没有去看其他题，以至于 t3 送的插头 dp 的 50 分没有拿到。
在高分不能保证的时候还是要多去看看部分分。

T2:
两种做法通过值域分治拼起来，这两种做法在部分分上有所体现，自己也都能想到。
但是合并的方式比较神奇，还没太看懂。

T3:
首先是这场比赛一直在莽 T1 几乎没怎么思考这道题。
50 插头 dp 是送的。
然后对于多组询问，容易想到预处理前缀后缀拼起来。
至于更高的分数，则考虑不对一般的横平竖直的行列 dp ，观察到斜线的长度不满，对斜线 dp 。
正解还没看懂。