T1 冲刺NOIP2021模拟23 回文

一个暴力的想法是记录当前匹配到的坐标，暴力转移，这样是\(\mathcal O(n^4)\) 的。

考虑优化，我们发现 dp 很多状态都是没有用的，于是想办法减少到三维。

每个坐标的步长值是确定的，所以我们只需考虑步长，每一步的坐标可以编号。

复杂度 \(\mathcal O(n^3)\)。

T2 冲刺NOIP2021模拟23 快速排序

根据伪代码，我们发现有数的部分最后一定是有序的。

于是只需要考虑每一个 nan 的位置即可。

模拟过程，记录到右边的也就是比当前小的权值的个数，遇到nan就赋上位置。

复杂度\(\mathcal O(nlogn)\)。

冲刺NOIP2021模拟23 混乱邪恶

将原数排序，奇数补 0。然后两两一组确定符号。

可以发现在题目的要求下一定有解。

冲刺NOIP2021模拟23 校门外歪脖树上的鸽子

考虑修改查询的实质，其实就是给一条链，然后对兄弟操作。

树链剖分，开两颗线段树记录链上的点分别为左右儿子时兄弟的贡献。

注意边界，最下面的点要从左端点然后一路向上是左儿子，注意不能超过lca。

右边同理。

修改链时注意lca及其左右儿子都不操作。

注意特判区间是一个单点。

注意根节点的兄弟赋值成自己，并且建树赋系数时要特判。

复杂度 \(\mathcal O(nlog^2n)\)。