2/11考试总结

时间安排

7:30–7:50 读题，T1貌似是个 dp ，T2 数据结构，T3 可能是数据结构。
7:50–9:45 T1，点规模非常大，可以达到 1e18 级别，感觉应该没法直接做，考虑每条新增的边的贡献，想到用 vector 暴力维护一条边两边的集合大小。写完发现是个假的。仔细想了一下发现直接做就是对的，有用点比较少，可以直接用 map 暴力存，然后暴力做。
9:45–10:51 T2,对于 n 比较小的时候可以单调栈暴力做，容易发现每一个新增的 r 的贡献只和单调栈中的一段有关，且每一段对应一个函数关系，可以用李超树无脑维护拿到 50 分。思考正解能否扫描线做，发现并不好维护。
10:50–12:00 T3,考虑写暴力，然后发现数据范围卡的太死了，不精细的暴力压根跑不动，于是一直在卡常。

回顾反思

T1:
一开始写的假做法耽误了一点时间。
对于这种规模极大的题要么是有某种神仙性质使得可以直接计算或者极大的缩小规模，要么就是只用考虑有用的点而这些点非常少。
T2:
比赛的时候更多的时间是在写部分分，部分分可以类似扫描线做，于是就去往扫描线直接处理区间答案想了，而正解则是考虑每个单独元素对区间的贡献。
不管是扫描线还是什么直接维护每个询问对应区间的答案不好做。发现题目的取 max 有可加性，于是可以考虑原序列每个元素对询问的贡献。可以单调栈处理出一个值为最值的区间 a,b ，那么最值就成了常量，可以讨论 [a,b] 与询问区间 [l,r] 的包含相交关系分四类讨论，可以使用二维数点、李超树等简单数据结构分四种做法计算。
T3:
比赛的时候几乎没给这道题时间，更多的时间是在卡暴力的常数。有类似的 dfs 的想法，但是觉得复杂度不可能对就没再想了。对于 dfs 的实现上，我的大致想法是比较暴力的，直接考虑枚举每一位，而正解则观察到 dfs 的过程是个 dag ，每次同时处理一层出边上的点，起到一个剪枝的效果。
正解实际上是个爆搜。考虑拓展时形成了一个dag结构，于是用vector存储当前的一些出边 dfs 跑 dag 。通过剪枝和主席树对于信息获取加速，复杂度就对了。

T1是送分题，T2也是没有任何代码难度的经典题，T3是 dfs，可能实现和剪枝上有一些细节和技巧，但是写了dfs 起码也是能够拿到 50 左右的。前两题都是应该 AC 的。尤其是这种 T1 应该尽可能减少花在上面的时间。