2 月做题记录

1 P14945

原神怎么你了。

这个问题经典难做，值域比较小，启发我们向 bitset 角度思考。

对横轴猫树分治，求跨过中点询问答案时，对左右分别扫描线，只需要分别求中点左右两侧的区间或，然后或在一起即可。

直接用线段树维护，那么查询一次是 \(O(\dfrac{n\log n}{w})\) 的，考虑扫描线过程怎么做。

先分析加入次数，根据分治需要加入的行数显然是 \(O(n\log n)\) 的。如果 \(O(\dfrac{n^2}{w})\) 直接重构线段树复杂度至少为 \(O(\dfrac{n^3\log n}{w})\)，无法接受。

考虑底层分块，其实意思就是你发现对深度很大的点 pushup 时还用左右儿子的或需要 \(O(\dfrac{n^2}{w})\)，而暴力访问区间所有点只需要 \(O(l)\) 的复杂度。平衡一下，设阈值 \(B\)。对于区间长度小于等于 \(B\) 的暴力遍历，否则上传。分析复杂度，第二类上传次数 \(O(\dfrac{n}{B})\)，复杂度 \(O(\dfrac{n^2}{Bw})\)。第一类每个大小为 \(B\) 的极大子树总访问次数 \(O(B \log B)\)，总共 \(O(\dfrac{n}{B})\) 个极大子树，复杂度 \(O(n\log B)\)。所以扫描线每加一行复杂度 \(O(\dfrac{n^2}{Bw}+n\log B)\)。取 \(B=O(\dfrac{n}{w})\) 可以令复杂度取到理论最优 \(O(n\log \dfrac{n}{w})\)。这样总复杂度 \(O(n^2\log n\log\dfrac{n}{w}+\dfrac{qn\log n}{w})\)，足以通过。

2 P14931

注意到除了最后一段外总能使得最大值就是段内最后一个数，显然这不劣并且容易证明可以取到。

那么枚举一段后缀后，前面的直接取前 \(k-1\) 大的数求和。

考虑选的后缀的最大值和前缀内第 \(k\) 大值的大小关系，若后缀最大值较大则选取的所有数就是整个序列前 \(k\) 大的，否则相当于整个序列前 \(k-1\) 大加上后缀的最大值。枚举 \(k\) 之后只会贡献给 \(k\) 和 \(k+1\) 的答案。总复杂度 \(O(n\log n+q)\)，瓶颈在于排序。

3 P15094

思考一会 polylog 感觉不太可做，考虑根号做法。

有一些思路，一个是对操作一涉及到的位置个数根号分治，一个是对序列分块，还有一个是考虑到操作一本质在维护一个集合 \(S\)，支持加入删除，查询区间和 \(S\) 交的本质不同颜色数，所以考虑能不能操作分块。

根号分治不是很好做，由于有序列的单点修改所以每种颜色出现次数是会变化的，相对不容易处理。先考虑序列分块。

对于带修区间数颜色，经典做法是维护每个位置之前的最靠后的与其同色位置。对于 \(i\) 记其为 \(p_i\)，询问区间 \([l,r]\) 即求 \(\sum \limits_{i=l}^r [p_i<l]\)。对于这个题，操作一维护了一个集合 \(S\)，支持向 \(S\) 内加入删除，查询的是 \(\sum \limits_{i=l}^r [p_i<l]\times [a_i \in S]\)。对序列单点修改只会影响 \(O(1)\) 个 \(p\)。

序列分块之后，将查询区间 \([l,r]\) 拆为整块和散块，散块容易维护，整块则需要求这一块内所有颜色的 \(p\) 的最小值中有多少数比 \(l\) 小。对于一类修改，对于每一块相当于删除或插入一种颜色。有 \(O(n\sqrt n)\) 次单点修改和前缀求和，只能做到 \(O(n \sqrt n \log n)\)。

另一个思考角度是操作分块，看起来是有道理的。序列的单点修改是相对简单的，故考虑只对一类操作分块，也就是考虑本次询问和上个关键点的 \(S\) 的对称差，大小为 \(O(\sqrt n)\)，只需要对于其中每种颜色判定其目前是否在区间 \([l,r]\) 中出现，以及当时是否在区间 \([l,r]\) 中出现。现在问题变为每种颜色维护一个序列，支持总共 \(O(n)\) 次单点修改和 \(O(n\sqrt n)\) 次区间求和，这时就可以分块平衡了。由于不可能对每种颜色维护长度为 \(n\) 的序列，所以把这种颜色出现过的位置拉出来离散化后再分块就行。时间复杂度 \(O(n\sqrt n)\)，空间看起来不难做到线性。

4 P15088

我们声称 \(n \geq 2 |\Sigma|\) 时先手必败。所以做法很简单，在本题中，\(n\geq 20\) 则先手必败，\(n<20\) 直接搜就行。

证明：

对 \(|\Sigma|\) 归纳。

\(|\Sigma| = 1\) 时显然，对于 \(|\Sigma|>1\)，只需要证明 \(n=2|\Sigma|\) 和 \(n=2|\Sigma|+1\) 时先手必败，\(n > 2|\Sigma|+1\) 时最后一定会操作到 \(n=2|\Sigma|\) 或 \(n=2|\Sigma|+1\)。

\(n = 2|\Sigma|\) 时，如果先手删去的出现一次或两次，操作后 \(|\Sigma|\) 至少减 \(1\)，如果删去的超过两次，则原字符串必定存在出现次数为 \(1\) 的字符，后手将其删去，\(|\Sigma|\) 也减 \(1\)。

\(n=2|\Sigma|+1\) 时，前面的分析同理，唯一不同的是删去的若出现次数为 \(3\)，则有可能剩下所有字符出现次数均为 \(2\)。我们声称每种字符均出现两次时且后手首先进行操作时，先手必败。同理对字符集大小归纳。\(|\Sigma|=1\) 时显然，否则后手删去第一个字符的第二次出现位置，之后每次操作先手若删去和后手一开始删的相同的则归纳到子问题，否则先手每删一个后手就删与其相同的。而除去第一个后的这个后缀是一个 \(n=2|\Sigma|\) 的子问题，先手不可能全删空。故后手必胜。

5 P14990

不难看出确定 \(S,T\) 后只需要将对应行列全染成同色即可最小化不美观度，答案即为 \(a,b \notin S\) 且 \(c,d \notin T\) 的满足条件四元组 \((a,b,c,d)\) 个数。

直接枚举所有满足条件四元组，直接做高维前缀和状物即可做到 \(O(2^{n+m}(n+m))\)，很蠢。

枚举 \(S\)，枚举四元组 \(a,b,c,d\)，将问题转到 \(T\) 一维上，现在相当于要做高维前缀和，但是初始非 \(0\) 的位置 \(w_i\) 必定满足 \(|i|=2\)。即对于所有 \(T\) 求 \(\sum \limits_{x<y,x\in T,y\in T} w_{x,y}\)。

记其为 \(f_T\)。考虑每次删去 \(T\) 的 \(\mathrm{lowbit}\)。

有 \(f_T=f_{T\setminus\{\mathrm{lowbit}(T)\}}+\sum \limits_{x \in T,x \neq \mathrm{lowbit}(T)} w(\mathrm{lowbit}(T),x)\)。

只需要求 \(\sum \limits_{x \in T,x \neq \mathrm{lowbit(T)}} w(\mathrm{lowbit}(T),x)\)。记其为 \(g_T\)，每次从 \(T\) 中删去除 \(\mathrm{lowbit}\) 后最低的 \(1\) 即可递推。

总复杂度 \(O(2^{n+m}+2^nn^2m^2)\)。

6 P15020

感觉就是细节一堆的题。

每个子树合法的大概是一个区间或者 \(O(1)\) 个区间的并形态，找出区间的方法大概是和子树内的数的相对顺序有关，这玩意直接线段树合并或者 DFN 序上主席树上二分啥的就能做。

7 P15011

问题结构显然是网络流类型。将所有点放在左边，掩体放在右边，左侧连 \(p_i\) 的边，右侧连 \(c_i\) 的边。二分答案 \(x\)，如果点 \(u\) 到掩体 \(v\) 最短路不超过 \(x\) 则连接左侧 \(u\) 到右侧 \(v\)。如果图存在左侧完美匹配则可行否则不可行。

直接跑网络流不是很优秀，考虑 Hall 定理。只需要对于左侧任意集合，\(\sum p\) 小于等于右侧邻域的 \(\sum c\)。也就是对于右侧每个集合 \(S\)，考虑左侧所有邻域包含于 \(S\) 的点都会被选入左侧集合，这个就是高维前缀和形态，直接做就行。复杂度 \(O(s2^s\log V)\)。

8 P15044

在 DFN 序上上一个带修区间线性基就行。

9 P15066

对右端点扫描线，对每个左端点 \(i\) 维护 \(c_i\) 表示 \([i,r]\) 的区间 \(\gcd\)。显然答案的左端点 \(i\) 满足 \(c_i \neq c_{i-1}\)，否则 \([i-1,r]\) 一定更优。当 \(r\) 固定时这样的 \(i\) 只有 \(O(\log V)\) 个，证明显然。

由于询问的是子区间信息，所以还要对每个 \(i\) 维护到目前的 \(r\) 结果。对目前的 \(r\) 和一个关键点对应区间 \([i,r]\)，相当于将前缀 \([1,i]\) 内的权值和目前的值 chkmax，查询区间 \([l,r]\) 即扫到右端点 \(r\) 时查询点 \(l\) 的点权。直接线段树可以做到 \(O(n \log n \log V)\)，维护单调栈没准能做到更优。

10 CF2043G

考虑计算 \(a_i=a_j\) 的 \((i,j)\) 对数。

经典不能 polylog，考虑序列分块。

将区间拆成若干整块和两个散块，将二元对分类讨论为整块散块，整块整块，和散块散块三类。其中整块散块和散块散块都容易做，考虑整块整块怎么做。

维护 \(f_{i,j}\) 表示第 \(i\) 个整块与 \([i,j]\) 之间的整块的贡献。单点修改时，设其处于第 \(i\) 块，则所有形如 \(f_{x,y}\)，其中 \(x\leq i\)，\(y\geq i\) 的值都会进行修改，对于 \(x<i\)，相当于对 \(y\geq i\) 的所有 \(f_{x,y}\) 整体加上某个值。直接用 poylog 数据结构维护后缀加只能做到 \(O(n\sqrt n \log n)\)。考虑询问只需要求形如 \(\sum \limits_{i=l}^r f_{i,r}\)。枚举一个块 \(j \in [l,r]\)，只需要计算其对 \(i \in [l,j]\) 之间的所有 \(f_{i,r}\) 贡献和，而对于这样的贡献我们只要求 \(r \geq j\)，其具体是多少只和 \(i\) 有关。故可以记 \(g_{x,j}\) 表示第 \(j\) 块对 \(i \in [x,j]\) 的所有 \(f_{i,j}\) 贡献和。修改块 \(j\) 时依次处理每个 \(i \leq j\) 的 \(g_{i,j}\) 的更新即可。这样复杂度就是 \(O(n\sqrt n)\) 的了。