AT和CF题

CF797E

根号分治，预处理一个 \(f_{p, k}\) 表示询问 \(p, k\) 需要的操作次数答案。

CF337D

点分树模板。

现学的点分树，思路是对于每棵子树以重心为根重建完预处理出 \(sgt\) 和 \(ch\) 两棵线段树，分别用于查询子树内距离重心距离为 \([l, r]\) 的点的个数和重心的父亲在原树上距离为 \([l, r]\) 的点的个数。

查询和修改的时候容斥即可。模板题P6329。

CF 上交有点卡常。

CF432D

考虑怎么刻画既是前缀也是后缀，考虑采用一种常用的套路令 \(T = S + \$ + S\)，\(S[1 \sim n - i + 1] = S[i \sim n]\) 可以转化为 \(T[1 \sim n - i + 1] = T[i + n + 1 \sim 2n + 1]\)。即当 \(Z[i + n + 1] = n - i + 1\) 时，\(T[i + n + 1 \sim 2n + 1]\) 是一个答案。

对于出现次数我们只需要统计 \(Z[j] \geq n - i + 1, j\in [n + 1, 2n + 1]\) 的 \(j\) 的个数即可。

CF27E

神秘暴搜题。

显然答案一定是 \(2^{k_1} \times 3^{k_2} \times 5^{k_3}...\) 的形式，并且每个 \(k_i \geq k_{i + 1}\)。

CF165E

容易发现对于每个 \(x\) 的答案一定出自 \(x\) 取反后的子集，于是使用高维前缀和做一下即可。

CF1442D

好题啊，首先发现这个东西是一个分组背包模型，但显然没办法直接做。

但你会发现题目给出了单调性，于是我们有这样一个性质：至多有一个数组没完全取完。

考虑反证，设有两个没满。不妨假设是 \(i, j\)，且这两个数组分别是 \(a_{i, p_1}, a_{i, p_1 + 1}, a_{i, p_1 + 2}\) 和 \(a_{j, p_2}, a_{j, p_2 + 1}, a_{j, p_2 + 2}\)。

那么我们现在的贡献是 \(a_{i, p_1} + a_{i, p_1 + 1} + a_{j, p_2} + a_{j, p_2 + 1}\)，假设让其中一个取满那贡献是 \(a_{i, p_1} + a_{i, p_1 + 1} + a_{i, p_1 + 2} + a_{j, p_2}\) 或 \(a_{i, p_1} + a_{j, p_2} + a_{j, p_2 + 1} + a_{j, p_2 + 2}\)。

作差分别为 \(a_{i, p_1 + 2} - a_{j, p_2 + 1}\) 和 \(a_{j, p_2 + 2} - a_{i, p_1 + 1}\)，二者一定有一个大于等于 \(0\)，所以取满更优。

然后这个问题变成了有一个数组取满或不取满，其它数组一定取满，这样两边的数组就变成了 \(01\) 背包。但还是不能直接枚举，因为这样其实做了很多无用的计算。

考虑进行分治，则没取满的一定在一边，而另一边不论如何都不会变，只需要计算一次即可，这样复杂度就对了。