一、题目重述

定义对字符串 $t$（长度 $\ge 2$，仅含数字 $1$–$9$）的压缩操作：

• 将 $t$ 分成偶数个非空子串 $t_1, t_2, \dots, t_m$（$m$ 为偶数）
• 输出 $t_2$ 重复 $t_1$ 次，$t_4$ 重复 $t_3$ 次，……

设 $f(t)$ 为通过这种方式能得到的最小结果字符串的长度。

给定字符串 $s$（长度 $n$，数字 $1$–$9$）和整数 $k$（$2 \le k \le n$），求 $s$ 所有长度为 $k$ 的连续子串的 $f$ 值。

---

二、操作的本质

一次操作的形式为：

输入：$t = t_1 t_2 t_3 t_4 \dots t_{m-1} t_m$（$m$ 为偶数）
输出：$\underbrace{t_2 t_2 \dots t_2}_{t_1 \text{次}} \ \underbrace{t_4 t_4 \dots t_4}_{t_3 \text{次}} \ \dots$

输出字符串的长度为：

$$\text{len} = |t_2| \times (\text{数值} t_1) + |t_4| \times (\text{数值} t_3) + \dots $$

其中 $|t_{2i}|$ 是子串 $t_{2i}$ 的长度，数值 $t_{2i-1}$ 是子串 $t_{2i-1}$ 对应的整数（因为子串只含数字 $1$–$9$，没有前导零问题）。

---

三、最小化长度的贪心策略

为了最小化最终长度，我们希望：

• 重复次数 $\text{数值} t_{2i-1}$ 尽可能小
• 被重复的子串长度 $|t_{2i}|$ 尽可能小

最小的正整数值是 $1$（对应数字 "1"），最小的子串长度也是 $1$（一个字符）。

因此，最优方案中，每个 $t_{2i-1}$ 和 $t_{2i}$ 都应该只包含一个字符。

于是，我们将 $t$ 分成若干个相邻的字符对：

$$(t_1, t_2),\ (t_3, t_4),\ \dots$$

每对 $(x, y)$ 贡献的长度为 $1 \times (\text{数值} x) = x$（因为 $y$ 被重复 $x$ 次，$|y|=1$）。

结论：

$$f(t) = \sum_{\text{每对}} (\text{第一个字符的数值})$$

---

四、长度为奇数的情况

如果 $t$ 的长度 $k$ 是奇数，无法恰好分成整数对。此时必须去掉一个字符（使其长度变为偶数），再按上述方式配对。

去掉的字符可以是第一个或最后一个（因为去掉中间的字符会导致剩余部分不连续，而我们的操作要求子串连续，所以只能去掉两端）。

因此：

• 去掉第一个字符，对剩余部分 $t[2..k]$ 计算偶数长度公式
• 去掉最后一个字符，对剩余部分 $t[1..k-1]$ 计算偶数长度公式
• 取两者最小值

---

五、数学公式

设子串为 $t = s[l..r]$，长度为 $k = r-l+1$，下标从 $1$ 开始。

定义：

• $p_{\text{odd}}[i]$：前 $i$ 个字符中，**奇数位置（1-based）**上的数字值之和
• $p_{\text{even}}[i]$：前 $i$ 个字符中，**偶数位置（1-based）**上的数字值之和

5.1 当 $k$ 为偶数

子串 $[l, r]$ 的奇数位置（相对于子串本身）在全局中的奇偶性取决于 $l$ 的奇偶性：

• 若 $l$ 为奇数：子串的奇数位置 = 全局奇数位置
• 若 $l$ 为偶数：子串的奇数位置 = 全局偶数位置

因此：

$$f(t) = \begin{cases} p_{\text{odd}}[r] - p_{\text{odd}}[l-1], & \text{if } l \text{ is odd} \\ p_{\text{even}}[r] - p_{\text{even}}[l-1], & \text{if } l \text{ is even} \end{cases} $$

5.2 当 $k$ 为奇数

去掉第一个字符：考虑子串 $[l+1, r]$，长度为 $k-1$（偶数），其 $f$ 值按偶数公式计算，但要注意此时 $l+1$ 的奇偶性。

去掉最后一个字符：考虑子串 $[l, r-1]$，长度为 $k-1$（偶数），按偶数公式计算。

最终：

$$f(t) = \min\big( \text{偶数情况}([l+1, r]),\ \text{偶数情况}([l, r-1]) \big) $$

---

六、前缀和预处理

我们预处理两个数组：

$$\text{odd}[i] = \sum_{j=1, j \text{ odd}}^{i} (s[j] - '0') $$$$\text{even}[i] = \sum_{j=1, j \text{ even}}^{i} (s[j] - '0') $$

递推公式：

$$\begin{aligned} \text{odd}[i] &= \text{odd}[i-1] + (i \% 2 == 1 ? (s[i]-'0') : 0) \\ \text{even}[i] &= \text{even}[i-1] + (i \% 2 == 0 ? (s[i]-'0') : 0) \end{aligned} $$

---

七、算法步骤

1. 读入 $n, k$ 和字符串 $s$（下标从 $1$ 开始）。
2. 计算前缀和数组 $\text{odd}[0..n]$ 和 $\text{even}[0..n]$。
3. 对每个起始位置 $l = 1$ 到 $n-k+1$：
   • 令 $r = l + k - 1$
   • 如果 $k$ 为偶数：
     • 若 $l$ 为奇数：$ans = \text{odd}[r] - \text{odd}[l-1]$
     • 若 $l$ 为偶数：$ans = \text{even}[r] - \text{even}[l-1]$
   • 如果 $k$ 为奇数：
     • 去掉最后一个字符：
       若 $l$ 为奇数：$opt1 = \text{odd}[r-1] - \text{odd}[l-1]$
       若 $l$ 为偶数：$opt1 = \text{even}[r-1] - \text{even}[l-1]$
     • 去掉第一个字符：
       若 $l+1$ 为奇数（即 $l$ 为偶数）：$opt2 = \text{odd}[r] - \text{odd}[l]$
       若 $l+1$ 为偶数（即 $l$ 为奇数）：$opt2 = \text{even}[r] - \text{even}[l]$
     • $ans = \min(opt1, opt2)$
   • 输出 $ans$

---

八、复杂度分析

• 前缀和预处理：$O(n)$
• 每个询问：$O(1)$
• 总复杂度：$O(n)$，完美满足 $n \le 2\times 10^5$ 的限制。

---

九、最终代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    
    vector<int> odd(n + 1, 0), even(n + 1, 0);
    
    for (int i = 1; i <= n; ++i) {
        int val = s[i - 1] - '0';
        odd[i] = odd[i - 1] + (i % 2 == 1 ? val : 0);
        even[i] = even[i - 1] + (i % 2 == 0 ? val : 0);
    }
    
    vector<int> ans;
    
    for (int l = 1; l <= n - k + 1; ++l) {
        int r = l + k - 1;
        
        if (k % 2 == 0) {
            if (l % 2 == 1) {
                ans.push_back(odd[r] - odd[l - 1]);
            } else {
                ans.push_back(even[r] - even[l - 1]);
            }
        } else {
            int opt1, opt2;
            if (l % 2 == 1) {
                // 去掉最后一个字符 [l, r-1]
                opt1 = odd[r - 1] - odd[l - 1];
                // 去掉第一个字符 [l+1, r]
                opt2 = even[r] - even[l];
            } else {
                opt1 = even[r - 1] - even[l - 1];
                opt2 = odd[r] - odd[l];
            }
            ans.push_back(min(opt1, opt2));
        }
    }
    
    for (int i = 0; i < (int)ans.size(); ++i) {
        cout << ans[i] << " \n"[i == (int)ans.size() - 1];
    }
    
    return 0;
}

---

十、正确性验证

• 偶数长度时，直接取奇数位置数字之和，符合贪心配对策略。
• 奇数长度时，枚举去掉首或尾的两种情况，取最小值。
• 通过前缀和 $O(1)$ 计算区间和，保证高效。