AT_agc072_b.[AGC072B] AGC Language

AGC 语是指仅由相同数量的 A 和 C 组成，且任意前缀中 A 的数量都不少于一半的长度不少于 $2$ 的字符串。现给定一个由 $N$ 个 A 和 $N$ 个 C 组成的 $2N$ 长度的字符串 $S$，请你针对 $k = 1, 2, \dots, K$ 回答以下问题：

在黑板上写下 $S$ 重复 $k$ 次得到的字符串。你可以按以下顺序进行操作，使黑板上的字符串变为 AGC 语。

1. 仅进行一次如下操作：
   • 选择整数 $(l, r)$，$1 \leq l \leq r \leq 2kN$，将字符串第 $l$ 到第 $r$ 个字符的子串反转。
2. 可以进行零次或多次如下操作：
   • 交换字符串中相邻的两个字符。

请计算最少需要多少次交换操作。

前缀的定义为：字符串 $Y$ 是字符串 $X$ 的前缀，当且仅当 $1 \leq |Y| \leq |X|$，且 $X$ 的前 $|Y|$ 个字符等于 $Y$。例如，ATC 是 ATCODER 的前缀，但 AGC 和 ATCODERGRANDCONTEST 都不是 ATCODER 的前缀。

输入以如下格式从标准输入读入：

$N$ $K$ $S$

请输出 $K$ 行，第 $i$ 行输出当 $k = i$ 时的答案。

限制条件

• $1 \leq N \leq 1\,000\,000$
• $1 \leq K \leq 300\,000$
• 字符串 $S$ 由 $N$ 个 A 和 $N$ 个 C 组成，长度为 $2N$
• $N$ 和 $K$ 均为整数

样例解释 1

当 $k = 1$ 时，黑板上最初写下的字符串为 AC。当 $k = 2$ 时，最初写下的字符串为 ACAC。两种情况下，字符串本身就是 AGC 语，因此例如选择 $(l, r) = (1, 1)$，可以通过 $0$ 次交换操作达成目标。

样例解释 2

当 $k = 1$ 时，黑板上写下的字符串为 CACAAACCCA。可以按以下步骤操作，仅需 $1$ 次交换操作：

1. 选择 $(l, r) = (1, 4)$，将第 $1$ 到 $4$ 个字符反转，得到字符串 ACACAACCCA。
2. 交换第 $9$ 个和第 $10$ 个字符，得到字符串 ACACAACCAC，这是一个 AGC 语。

由 ChatGPT 4.1 翻译