CF2206F Minesweeper String

给定一个由数字 $0$ 到 $9$ 组成的字符串 $S$，长度为 $n$。你需要用这个字符串生成一个变种的扫雷游戏。在这个变种中，一个格子可以包含多个地雷，并且每个格子的地雷数是基于其“4 邻域”（与其边相邻的格子），而不是传统的 8 邻域。 具体过程如下： 你选择一个整数 $w$（$1 \le w \le n$）作为网格的宽度。将 $n$ 个格子（编号 $0$ 到 $n-1$）按顺序排列成网格。网格共有 $\left\lceil n / w \right\rceil$ 行（从上到下编号为 $0$ 到 $\left\lceil n / w \right\rceil-1$），和 $w$ 列（从左到右编号为 $0$ 到 $w-1$）。对于每个 $0 \leq i < n$，编号为 $i$ 的格子位于第 $\left\lfloor i/w \right\rfloor$ 行、第 $i \bmod w$ 列，并对应 $S$ 的第 $(i+1)$ 位数字。因此，第 $0$ 行包含格子 $0$ 到 $w-1$，第 $1$ 行包含格子 $w$ 到 $2w-1$，以此类推。注意，最底下一行可能不足 $w$ 个格子。 将格子排列好后，进行如下两步： 1. 对于对应于非零数字 $x$（$1$ 到 $9$）的格子，在该格子中放入 $x$ 个地雷。 2. 对于其余对应 $0$ 的格子，在该格子里填写一个数字，表示与其相邻的所有格子中地雷的总数。两个格子相邻当且仅当它们有共同的边。每个格子至多有四个相邻的格子。 对于每个宽度 $w$，定义 $f(w)$ 为所有没有地雷的格子中填写数字之和。给定整数 $k$，问 $f(1), f(2), \ldots, f(n)$ 这 $n$ 个值中的第 $k$ 大值是多少。

第一行输入两个整数 $n$ 和 $k$（$1\leq k \leq n \leq 500\,000$）。 第二行输入一个长度为 $n$ 的，仅包含数字 $0$ 到 $9$ 的字符串 $S$。

输出 $f(1), f(2), \ldots, f(n)$ 中的第 $k$ 大的值。

示例输入输出 #1 说明 下图展示了所有 $5$ 种宽度下的网格。每个格子的点表示一个地雷。  图 F.1：所有 $5$ 种可能的宽度下生成的网格。 将所有没有地雷格子的数字相加，可以得到如下结果： - $f(1) = 7$ - $f(2) = 3$ - $f(3) = 11$ - $f(4) = 4$ - $f(5) = 7$ 第 $3$ 大的值为 $7$。 由 ChatGPT 5 翻译