Binary Sequence and Queries

For convenience, use indices from $0$ to $N-1$, with every index interpreted modulo $N$.

Applying the operation twice at the same starting position cancels out. Therefore it is enough to let $x_i\in\{0,1\}$ denote whether the operation starting at $i$ is used an odd number of times.

For position $i$ to become 0, we need

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

XORing the equations for two adjacent positions gives

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

Let $d=\gcd(N,K)$, $m=N/d$, and $h=K/d$. The permutation splits the indices into exactly cycles, each of length .

For a residue class $r$, define

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

The XOR of all difference equations in one cycle is $P_r\oplus P_{r-1}$. Thus the difference equations are consistent if and only if

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

Write one cycle in the order

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

Choose the canonical solution

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

Let $c_r$ be the number of ones among the $x$ values in cycle $r$.

Considering only the difference equations, every cycle has one free variable $y_r$ that flips the entire cycle. The cost is $c_r$ for $y_r=0$ and for . Hence the minimum cost for the difference equations alone is

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

The difference equations used only differences of the original equations, so one original equation must still be enforced. For position $0$, define the residual

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

We need $E=0$.

A length-$K$ window contains exactly $h=K/d$ indices from every residue class.

If $h$ is even, flipping an entire cycle does not change $E$. Therefore $E=1$ is impossible, while for $E=0$ the answer is $B$.

If $h$ is odd, each $y_r$ toggles $E$ once, so

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

Let the cheaper choice for each cycle be

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

If $Z=E$, the answer is $B$. Otherwise one cycle must take the opposite choice, at an extra cost of

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

Now consider a query. Flipping $a_p$ toggles only $\Delta_p$ and $\Delta_{p+1}$, and it toggles only . Thus the condition that all are equal can be checked in by maintaining the number of classes with .

Inside a cycle, toggling $\Delta_{v_s}$ with $s\ge1$ flips the suffix

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

of the canonical solution. When $s=0$, $\Delta_{v_0}$ is used only by the cycle-closing consistency equation, so the canonical values themselves do not change.

Concatenate all cycles in cycle order into one array of length $N$. A lazy segment tree supports range flips and range-one-count queries. Every query needs at most two suffix flips and recomputation of $c_r$ for at most two affected cycles.

Whenever a $c_r$ changes, maintain the following values.

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

The residual $E$ can also be updated instead of recomputed. Precompute $impact[u]$, the parity of the number of positions in the affected canonical suffix for $\Delta_u$ that lie in the length-$K$ window of . For a cycle root, . A query at updates

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

Therefore the answer to each query is:

• -1 if the $P_r$ values are not all equal;
• if $h$ is even, -1 when $E=1$, otherwise $B$;
• if is odd, .

Preprocessing each test case takes $O(N\log N)$ time, and each query takes $O(\log N)$ time. The total complexity is $O((N+Q)\log N)$ with memory.

Solution written by GPT5.6