二进制序列与查询

以下使用 $0$ 到 $N-1$ 的下标，并把所有下标按模 $N$ 解释。

在同一个起点执行两次操作会互相抵消。因此只需令 $x_i\in\{0,1\}$ 表示是否在位置 $i$ 开始的操作被执行奇数次。

为了让位置 $i$ 最终变成 0，必须满足

$$a_i=\bigoplus_{j=i-K+1}^{i}x_j.$$

将相邻两个位置的方程异或，得到

$$x_i\oplus x_{i-K}=\Delta_i,\qquad \Delta_i=a_i\oplus a_{i-1}.$$

令 $d=\gcd(N,K)$、$m=N/d$、$h=K/d$。映射 会把所有下标分成恰好 个长度为 的环。

对余数类 $r$ 定义

$$P_r=\bigoplus_{i\equiv r\pmod d}a_i.$$

把一个环中的所有差分方程异或，结果为 $P_r\oplus P_{r-1}$。因此差分方程有解当且仅当

$$P_0=P_1=\cdots=P_{d-1}.$$

把一个环按

$$v_t=r+tK\pmod N,\qquad t=0,\ldots,m-1$$

的顺序排列。选取 canonical 解

$$x_{v_0}=0,\qquad x_{v_t}=x_{v_{t-1}}\oplus\Delta_{v_t}\quad(t\ge1).$$

记环 $r$ 中 $x=1$ 的个数为 $c_r$。

只考虑差分方程时，每个环都有一个自由变量 $y_r$，表示是否把整个环的 $x$ 全部翻转。$y_r=0$ 的代价是 ， 的代价是 。因此只满足差分方程的最小代价为

$$B=\sum_r\min(c_r,m-c_r).$$

差分方程只使用了原方程之间的差，所以还需要额外满足一个原方程。对位置 $0$ 定义残量

$$E=a_0\oplus\bigoplus_{j=-K+1}^{0}x_j.$$

目标是 $E=0$。

长度为 $K$ 的区间中，每个余数类恰好出现 $h=K/d$ 次。

若 $h$ 为偶数，翻转整个环不会改变 $E$。因此 $E=1$ 时无解，$E=0$ 时答案为 $B$。

若 $h$ 为奇数，每个 $y_r$ 都会把 $E$ 翻转一次，所以必须满足

$$y_0\oplus y_1\oplus\cdots\oplus y_{d-1}=E.$$

对每个环，按代价较小的一侧定义

$$z_r=[c_r>m/2],\qquad Z=\bigoplus_r z_r.$$

若 $Z=E$，答案就是 $B$。否则必须让某一个环选择另一侧，额外代价为

$$\min_r|m-2c_r|.$$

处理查询时，翻转 $a_p$ 只会翻转 $\Delta_p$、$\Delta_{p+1}$ 和 。因此只要维护 的余数类数量，就能在 时间判断所有 是否相等。

在一个环内，若翻转 $\Delta_{v_s}$ 且 $s\ge1$，canonical 解中的

$$x_{v_s},x_{v_{s+1}},\ldots,x_{v_{m-1}}$$

这一段 suffix 会全部翻转。当 $s=0$ 时，$\Delta_{v_0}$ 只用于环的闭合一致性条件，不会改变 canonical 解本身。

把所有环按环内顺序拼接成一个长度为 $N$ 的数组，使用支持区间翻转和区间 $1$ 个数查询的 lazy segment tree。每个查询最多进行两次 suffix 翻转，并重新计算至多两个受影响环的 $c_r$。

每当某个 $c_r$ 改变时，同时维护：

• $B=\sum_r\min(c_r,m-c_r)$

$E$ 也不需要每次重新计算。预处理 $impact[u]$，表示翻转 $\Delta_u$ 时被翻转的 canonical suffix 与 $E$ 使用的长度 区间相交位置数的奇偶性。环的起点满足 。对位置 的查询，

$$E\mathrel{\oplus}=[p=0]\oplus impact[p]\oplus impact[p+1].$$

因此每个查询的答案为：

• 若所有 $P_r$ 不相等，输出 -1；
• 若 $h$ 为偶数，$E=1$ 时输出 -1，否则输出 $B$；
• 若 $$ 为奇数，答案为 。

每个测试用例的预处理时间为 $O(N\log N)$，每个查询为 $O(\log N)$。总时间复杂度为 $O((N+Q)\log N)$，空间复杂度为 。

Solution written by GPT5.6