ZJCPC2025 补题

只补后面的题。

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

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

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

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

预处理 $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]$ 之间的答案（后缀同理）。至此一个询问还剩散块之间没处理，排序后双指针即可。