ZJCPC2025 补题

_jimmywang_ · 2025-10-08 13:38:20 · 个人记录

只补后面的题。

C.

首先答案的质因子一定来源于第一个数的质因子或其翻转，由此我们可以得到答案质因子个数不超过 \log。预处理此，然后分因子处理。

对于一个质因子的某次方 p^a，棋盘中每个位置无外乎 4 种情况：必须翻、必须不翻、无所谓、翻和不翻都不行。最后一种直接让这个 p^a 倒闭，前两种则给出了能影响到这个格子的两条对角线之间的限制。将对角线视作点，限制连边，一个连通块若有解一定有两解（全翻一下），判定可以直接 dfs 染色。

维护一下每个连通块是否合法，以及每个 p^a，是否所有连通块都合法，然后把所有合法的 p^a \gcd 起来即可。修改是单点反转颜色，每个 p^a 只会修改 1 个连通块，单次询问复杂度是 O(\log) 的。

A.

变态啊，想了一晚上你告诉我分块。

预处理 f_i,g_i 表示必选 i 的前/后缀最大权 LIS。考虑答案只可能来自：

第一种 trivial，不管他。第二种分块。

预处理 pre_{i,j} 表示 i 及以前的块里的 \max_{a_k\le j}f_k， suf_{i,j} 表示i 及以后的块里的 \max_{a_k\le j}g_k。然后可用这两个信息得到前 i 块和 [j,m] 之间的答案（后缀同理）。至此一个询问还剩散块之间没处理，排序后双指针即可。