1. 操作转化

我们有一个长度为 $n$ 的 01 串 $a[1 \dots n]$。

一次操作：选择一个长度为 $k$ 的子区间 $[l, l+k-1]$，将其全部取反（0 变 1，1 变 0）。

取反就是异或 1。

---

2. 差分数组

定义差分数组：

$$d_i = a_i \oplus a_{i-1}, \quad i=1 \dots n+1$$

其中 $a_0 = 0, a_{n+1} = 0$。

那么 $d_i$ 也是 0/1。

初始时，$d_1 = a_1$，$d_{n+1} = a_n$（因为 $a_{n+1}=0$）。

---

3. 操作对差分数组的影响

考虑对区间 $[l, l+k-1]$ 取反：

• 对于 $a_l$：从 $a_l$ 变成 $\neg a_l$，而 $a_{l-1}$ 不变，所以 $d_l = a_l \oplus a_{l-1}$ 变成 $\neg a_l \oplus a_{l-1} = \neg (a_l \oplus a_{l-1}) = \neg d_l$。即 $d_l$ 取反。
• 对于 $a_{l+k-1}$：它变成 $\neg a_{l+k-1}$，而 $a_{l+k}$ 不变，所以 $d_{l+k} = a_{l+k} \oplus a_{l+k-1}$ 变成 $a_{l+k} \oplus \neg a_{l+k-1} = \neg (a_{l+k} \oplus a_{l+k-1}) = \neg d_{l+k}$。即 $d_{l+k}$ 取反。
• 对于中间的 $d_{l+1} \dots d_{l+k-1}$：$a_{j}$ 和 $a_{j-1}$ 同时取反，异或值不变，所以这些 $d_j$ 不变。

结论：一次操作只会翻转 $d_l$ 和 $d_{l+k}$ 这两个位置的值（异或 1）。

---

4. 目标状态

最终我们要让区间 $[L,R]$ 内的 $a_i$ 全为 0。

最终 $a_i=0$ 对所有 $i \in [L,R]$，且 $a_{L-1}=0$（区间外不变），$a_{R+1}=0$（区间外不变）。

那么差分数组最终状态：

• $d_L = a_L \oplus a_{L-1} = 0 \oplus 0 = 0$
• $d_{R+1} = a_{R+1} \oplus a_R = 0 \oplus 0 = 0$
• 对于 $i \in (L,R]$，$d_i = 0 \oplus 0 = 0$

所以目标：把 $d_L, d_{L+1}, \dots, d_{R+1}$ 全部变成 0。

---

5. 问题转化

现在问题变成：

• 我们有一个差分数组 $d[1 \dots n+1]$。
• 一次操作：选择 $l \in [1, n-k+1]$，翻转 $d_l$ 和 $d_{l+k}$。
• 给定区间 $[L,R]$，我们要翻转 $d_L \dots d_{R+1}$ 这些位置中的若干个（初始为 1 的位置），使得它们全为 0。
• 操作时 $l$ 和 $l+k$ 必须在 $[1, n+1]$ 范围内，但这里 $l$ 可以超出 $[L,R]$ 吗？注意操作区间是原序列的 $[l, l+k-1]$，可能部分在 $[L,R]$ 外，但题目允许选择区间内的任意子区间，所以 $l$ 必须在 $[L, R-k+1]$ 内？不对，仔细看：题目说“选择这个区间的一个长度为 k 的子区间”，所以 $l$ 必须在 $[L, R-k+1]$ 内。这意味着我们只能翻转 $d_l$ 和 $d_{l+k}$ 其中 $l \in [L, R-k+1]$。

---

6. 模 k 分组

因为一次操作翻转的两个位置下标差 $k$，所以我们可以按位置模 $k$ 的余数分组。

设余数 $r \in \{0,1,\dots,k-1\}$，但这里下标从 1 开始，我们考虑 $d$ 的下标 $i$，令 $r = (i-1) \bmod k$。

那么一次操作会挑选同一组内的两个位置（相差 $k$）进行翻转。

---

7. 可行性条件

对于区间 $[L,R]$，我们要翻转的 $d$ 位置是 $L \dots R+1$ 中初始为 1 的那些位置。

这些位置按模 $k$ 分组后，每组内 1 的个数必须是偶数，因为一次操作翻转组内的两个 1（或引入两个 1，但最终要消掉）。

所以：

可行性条件：对于每个余数 $r$，在 $d_L \dots d_{R+1}$ 中，属于该余数类且值为 1 的位置个数必须是偶数。

---

8. 最少操作次数

对于某一组（余数 $r$），设该组在 $[L,R+1]$ 范围内有 $c$ 个 1（$c$ 为偶数）。

我们可以在组内将这些 1 两两配对，每对 $(p, q)$ 可以通过从 $p$ 开始，长度为 $k$ 的操作链一路翻转到 $q$ 的位置，这需要 $(q-p)/k$ 次操作吗？不对，更准确地说：

一次操作 $(l, l+k)$ 翻转两个位置，如果它们相邻（在组内相邻 1），则一次操作消掉。如果它们不相邻，则需要多次操作传递 1：例如位置 $x$ 和 $x+k$ 操作后，1 移动到 $x+k$，再和 $x+2k$ 操作，1 移动到 $x+2k$，如此传递到目标位置。其实等价于在组内位置序列上，相邻两个 1 的距离（以 k 为单位）就是操作次数。

结论：对于一组内位置 $p_1 < p_2 < \dots < p_{2t}$（在 $[L,R+1]$ 内），最优配对是 $(p_1,p_2), (p_3,p_4), \dots$，操作次数 = $\sum_{j=1}^{t} \frac{p_{2j} - p_{2j-1}}{k}$。

因为每次操作只能移动 1 到 $+k$ 位置，所以两个 1 的位置差必须是 $k$ 的倍数，并且差除以 $k$ 就是所需操作次数。

---

9. 高效计算

我们需要对每个询问 $[L,R]$：

1. 检查可行性：对每个余数 $r$，在 $d_L \dots d_{R+1}$ 中该组 1 的个数为偶数。
2. 若可行，计算 $\sum_{r=0}^{k-1} \sum_{j=1}^{t_r} \frac{p_{2j} - p_{2j-1}}{k}$，其中 $t_r$ 是该组配对数。

---

10. 预处理与查询

我们可以预处理：

• 对每个余数 $r$，记录该组所有 1 的位置列表 $pos[r]$。
• 对每个余数 $r$，预处理前缀和，以便快速计算区间内 1 的个数（判断可行性）以及配对的代价。

具体地，对于一组内位置列表 $pos[r] = [x_1, x_2, \dots, x_m]$，我们定义：

• $cnt[r][i]$ = 前 $i$ 个位置的 1 的个数（其实就是 i）
• $sum[r][i]$ = 前 $i$ 个位置中，奇数位置减去偶数位置的位置和（用于快速计算配对距离和）。

实际上，配对距离和 = （所有偶数下标位置和）−（所有奇数下标位置和）。

所以我们可以预处理每个组的前缀奇偶位置和，然后 $O(1)$ 计算任意区间内的配对代价。

---

11. 查询过程

对询问 $[L,R]$，考虑 $d_L \dots d_{R+1}$：

对每个余数 $r$，用二分在 $pos[r]$ 中找到在 $[L,R+1]$ 内的所有 1 的位置，检查个数是否为偶数。

若全为偶数，则答案 = $\sum_{r=0}^{k-1} \left( \frac{\text{evenSum} - \text{oddSum}}{k} \right)$，其中 evenSum 是这些位置中偶数索引（在选中子序列中的索引）的和，oddSum 是奇数索引的和。

注意索引是在选中子序列中从 1 开始编号的。

---

12. 时间复杂度

• 预处理 $O(n)$
• 每组查询 $O(k \log n)$，因为对 k 个组分别二分。
• 总复杂度 $O(n + m k \log n)$，在 $k$ 小的时候可行，但 $k$ 可能很大（最大 $n$），需要优化。

实际上，$k$ 很大时，很多组在区间内没有 1，可以跳过。我们可以只处理在区间内有 1 的组。

---

13. 实现细节

• 注意 $d_{R+1}$ 也要考虑，它对应 $a_R$ 和 $a_{R+1}$ 的差分。
• 判断可行性时，如果 $L=1$，则 $d_1 = a_1$；如果 $R=n$，则 $d_{n+1} = a_n$。
• 配对时，在 $[L,R+1]$ 内的 1 的位置按升序配对。