2023/10/04 模拟赛 总结
时间安排
07:40 - 08:20
看题，写 A,B，感觉会 C。
08:20 - 08:40
写 C 暴力。
08:40 - 09:10
写换根部分，思考怎么不用平衡树。
09:10 - 10:10
写平衡树，调代码。拍 C。
10:10 - 10:20
写 D 暴力。
10:20 - 10:40
拍 A,B。
10:40 - 11:20
写 D 40分。
11:20 - 11:40
发呆。
总结反思
大愚若智。
交题前检查数据类型。
数据结构注意常数和边界。
题解
A.
暴力 dp。
B.
对质因数大小根号分治，状压。
C.
策略是不断往中间走，然后轮流拿最大子树。
路径权值可以换根。排名分别为奇偶的元素和可以用平衡树维护，但是太笨比了。发现每次最多删两个，对每个点奇偶前缀和。
D.
暴力思路是线段树分治后带线段树上二分和撤销。
但是空间时间都炸了。换成平衡树维护连续白色段可过。
std 是单侧递归线段树，就是 pushup 的时候暴力查询，但是只递归一侧。