← 返回题目列表

AtCoder · agc072_b

B. AGC 语言

中文机器翻译题面 查看原题

分数: 1100 点

问题陈述

AGC 字是长度至少为 2 包含相同数量的 A的和 C的,并且在每个前缀中, A至少占了一半的字符。 给你一个字符串 S 长度 2N 组成 N A的和 N C的。对于每个 k = 1, 2, \dots, K,回答以下问题。

黑板上显示了一个由以下内容串联而成的字符串 k 副本 S。 要将其转换为 AGC 字,请按顺序执行以下操作:

  1. 执行 正好一次:
    • 选择整数 (l, r) (1 \le l \le r \le 2kN) 并反转 l-th 通过 r- 字符串的第一个字符。
  2. 执行 零次或多次:
    • 交换字符串的两个相邻字符。

所需的最少交换次数是多少?

前缀注释 一个字符串 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的和 N C的。
  • 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。通过执行以下步骤,该序列仅需要一次交换:

  1. 选择 (l, r) = (1, 4) 并反转 1-st 通过 4个字符。字符串现在是 ACACAACCCA.
  2. 交换 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