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 翻译