分数: 1100 点
问题陈述
AGC 字是长度至少为 2 包含相同数量的 A的和 C的,并且在每个前缀中, A至少占了一半的字符。
给你一个字符串 S 长度 2N 组成 N A的和 N C的。对于每个 k = 1, 2, \dots, K,回答以下问题。
黑板上显示了一个由以下内容串联而成的字符串 k 副本 S。 要将其转换为 AGC 字,请按顺序执行以下操作:
- 执行 正好一次:
- 选择整数 (l, r) (1 \le l \le r \le 2kN) 并反转 l-th 通过 r- 字符串的第一个字符。
- 执行 零次或多次:
- 交换字符串的两个相邻字符。
所需的最少交换次数是多少?
前缀注释
一个字符串 Y 是前缀 X 当且仅当 1 \le |Y| \le |X| 和第一个 |Y| 的字符 X 等于 Y。 例如,ATC 是前缀 ATCODER,但是 AGC 和 ATCODERGRANDCONTEST 不是。
约束
- 1 \le N \le 1\,000\,000
- 1 \le K \le 300\,000
- S 是一个长度-2N 字符串组成 N
A的和 NC的。 - N 和 K 是整数。
输入
输入由标准输入按以下格式给出:
N K S
输出
打印 K 行。的 i第 行 (1 \le i \le K) 应包含以下问题的答案 k = i.
示例输入 1
1 2 AC
示例输出 1
0 0
对于 k = 1,初始字符串是 AC;
对于 k = 2,它是 ACAC.
两者都已经是 AGC 词,所以选择,说, (l, r) = (1, 1) 产量 0 交换。
示例输入 2
5 1 CACAAACCCA
示例输出 2
1
对于 k = 1,字符串是 CACAAACCCA。通过执行以下步骤,该序列仅需要一次交换:
- 选择 (l, r) = (1, 4) 并反转 1-st 通过 4个字符。字符串现在是
ACACAACCCA. - 交换 9-th 和 10个字符。字符串现在是
ACACAACCAC,这是一个 AGC 字。
示例输入 3
10 10 ACCCAAAACCCACCACAACA
示例输出 3
1 2 3 3 3 3 3 3 3 3
示例输入 4
50 10 ACCCCACAACAAAACCAACCCCACCAACACCAAAACACACAAAACCCCCACCAACACAACAACCCCAACAAACCCAACACACCCACACCAAACCCAAACA
示例输出 4
10 17 20 22 23 24 25 26 26 26
示例输入 5
72 10 CCCCACAAAAACCCACACCAAACCACCCCCAAAAACACCACCCCCAAAAAAACAAAAAACCCCCCACCCAAACAACACCACCACAAACCCAACCAACAACCCAAAACAACCCCACCACACACCACACCCACAAACACAACAACA
示例输出 5
28 42 51 54 57 60 63 64 65 66