Part 1

首先，通过模拟，不难发现：开奖过程实际上是在环形字符串 $P$ 中截取子串，并取第 $k$ 大字母（设 $\texttt{A}>\texttt{B}>\ldots>\texttt{Z}$）。

不难发现，最难处理的就是「第 $k$ 大」。于是，我们需要一条重要性质：

在一个含有不少于 $k$ 个数的序列中，任意一个数 $x$ 成为第 $k$ 大数的充分必要条件是：

设序列中大于 $x$ 的数共 $s$ 个，大于等于 $x$ 的数共 $t$ 个，则有 $s < k \le t$。

这个性质很显然，证明不给了。

Part 2

注意到 $|\Sigma| = 26$（$P$ 中最多有 $26$ 种字符），我们将每个字符分开处理。

先将 $P$ 复制一遍接到末尾。

对于某个字符 $c$，设 $s_i$ 为 $P_{1 \ldots i}$（$P$ 的前 $i$ 个字符）中大于 $c$ 的字符个数，$t_i$ 为 $P_{1 \ldots i}$（$P$ 的前 $i$ 个字符）中大于等于 $c$ 的字符个数。

显然，它们可以用前缀和处理，并且单调不降。

然后，枚举每个 $l$，依据上面性质查找符合要求的最小 $r$ 与最大 $r$，合法的 $r$ 即为两者之间的数，可以 $O(1)$ 统计答案。注意 $l+k-1 \le r \le l+n-1$。

可以发现，如果升序枚举 $l$，最小 $r$ 与最大 $r$ 单调不降，于是每次都可以从上次的位置接着升序枚举。

因此，每个字符可以做到 $O(p)$ 求解。总时间复杂度 $O(|\Sigma| \cdot\ p)$，空间复杂度 $O(p)$。

Part 3

std：

#include <iostream>
using namespace std;
const int PP = 2000005;
int l[PP], le[PP], pp[PP];
//  s[i]   t[i]    P
int p, k;
int lastf1 = 0, lastf2 = 0; // 上次查询的记录
int f1(int lf, int rg, int v) { // 最大 r：s <= k - 1
    if (l[lf] > v) return lf - 1; // 没有符合要求的 r
    while (l[lastf1 + 1] <= v && lastf1 < rg) lastf1 ++;
    return lastf1;
}
int f2(int lf, int rg, int v) { // 最小 r：t >= k
    if (le[rg] < v) return rg + 1; // 没有符合要求的 r
    while (le[lastf2] < v && lastf2 < rg) lastf2 ++;
    return lastf2;
}
int main() {
	cin >> p >> k;
	for (int i = 1; i <= p; i ++) {
            char c;
            cin >> c;
            pp[i] = pp[i + p] = c - 64; // 读入 + 复制 + A,B,C,...,Z 转为 1,2,3,...,26
        }
        for (int cases = 1; cases <= 26; cases ++) {
            lastf1 = lastf2 = 0;
            for (int i = 1; i <= p * 2; i ++) {
                l[i] = l[i - 1];
                le[i] = le[i - 1];
                if (pp[i] < cases) l[i] ++;
                if (pp[i] <= cases) le[i] ++;
            }
            long long ans = 0;
            for (int i = 1; i <= p; i ++)
                ans += max(f1(i + k - 1, i + p - 1, k + l[i - 1] - 1) - f2(i + k - 1, i + p - 1, k + le[i - 1]) + 1, 0);
            cout << ans << endl;
        }
	return 0;
}