B - AGC Language Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 1100 点

問題文

AGC 語とは、同じ数の A と C のみからなり、どの接頭辞についても A が半数以上を占める 2 文字以上の文字列を指します。 N 個の A と N 個の C からなる 2N 文字の文字列 S が与えられるので、k = 1, 2, \dots, K について次の問いに答えてください。

黒板に S を k 回繰り返した文字列が書かれている。 以下の操作をその順に行うことで、黒板の文字列を AGC 語にしたい。

  1. 次の操作を 1 回だけ行う。
    • 整数 (l, r) (1 \leq l \leq r \leq 2kN) を選択し、文字列の l から r 文字目までの部分を reverse する。
  2. 次の操作を 0 回以上行う。
    • 文字列の隣接する 2 文字を swap する。

最小何回の swap 操作が必要であるか、計算せよ。

接頭辞とは文字列 Y が文字列 X の接頭辞であるとは、1 \leq |Y| \leq |X| であり、かつ X の最初の |Y| 文字が Y であることを指します。たとえば ATC は ATCODER の接頭辞ですが、AGC や ATCODERGRANDCONTEST は ATCODER の接頭辞ではありません。

制約

  • 1 \leq N \leq 1\,000\,000
  • 1 \leq K \leq 300\,000
  • 文字列 S は N 個の A と N 個の C からなる 2N 文字の文字列である
  • N と K は整数

入力

入力は以下の形式で標準入力から与えられます。 

N K
S

出力

答えを K 行に出力してください。i 行目 (1 \leq i \leq K) には k = i のときの答えを出力してください。

入力例 1

1 2
AC

出力例 1

0
0

k = 1 のとき、最初黒板に書かれた文字列は AC となります。
k = 2 のとき、最初黒板に書かれた文字列は ACAC となります。

両方とも最初から AGC 語であるため、たとえば (l, r) = (1, 1) とすると、0 回の swap 操作を達成することができます。

入力例 2

5 1
CACAAACCCA

出力例 2

1

k = 1 のとき、黒板に書かれる文字列は CACAAACCCA となります。以下の手順で操作を行うと、swap 操作を 1 回しか行う必要がありません。

  1. (l, r) = (1, 4) を選択し、文字列の 1 から 4 文字目を reverse する。文字列は ACACAACCCA となる。
  2. 文字列の 9 文字目と 10 文字目を swap する。文字列は 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

Score : 1100 points

Problem Statement

An AGC word is a string of length at least 2 that contains the same number of A’s and C’s, and in every prefix, A’s make up at least half of the characters. You are given a string S of length 2N consisting of N A’s and N C’s. For each k = 1, 2, \dots, K, answer the following question.

A blackboard shows a string that is a concatenation of k copies of S. To turn it into an AGC word, perform the operations below in the order written:

  1. Perform exactly once:
    • Choose integers (l, r) (1 \le l \le r \le 2kN) and reverse the l-th through r-th characters of the string.
  2. Perform zero or more times:
    • Swap two adjacent characters of the string.

What is the minimum number of swaps required?

Notes on prefix A string Y is a prefix of X if and only if 1 \le |Y| \le |X| and the first |Y| characters of X equal Y. For example, ATC is a prefix of ATCODER, but AGC and ATCODERGRANDCONTEST are not.

Constraints

  • 1 \le N \le 1\,000\,000
  • 1 \le K \le 300\,000
  • S is a length‑2N string consisting of N A’s and N C’s.
  • N and K are integers.

Input

The input is given from Standard Input in the following format:

N K
S

Output

Print K lines. The i‑th line (1 \le i \le K) should contain the answer for k = i.

Sample Input 1

1 2
AC

Sample Output 1

0
0

For k = 1, the initial string is AC;
For k = 2, it is ACAC.

Both are already AGC words, so choosing, say, (l, r) = (1, 1) yields 0 swaps.

Sample Input 2

5 1
CACAAACCCA

Sample Output 2

1

For k = 1, the string is CACAAACCCA. By following the steps below, the sequence needs only one swap:

  1. Choose (l, r) = (1, 4) and reverse the 1-st through 4-th characters. The string is now ACACAACCCA.
  2. Swap the 9-th and 10-th characters. The string is now ACACAACCAC, which is an AGC word.

Sample Input 3

10 10
ACCCAAAACCCACCACAACA

Sample Output 3

1
2
3
3
3
3
3
3
3
3

Sample Input 4

50 10
ACCCCACAACAAAACCAACCCCACCAACACCAAAACACACAAAACCCCCACCAACACAACAACCCCAACAAACCCAACACACCCACACCAAACCCAAACA

Sample Output 4

10
17
20
22
23
24
25
26
26
26

Sample Input 5

72 10
CCCCACAAAAACCCACACCAAACCACCCCCAAAAACACCACCCCCAAAAAAACAAAAAACCCCCCACCCAAACAACACCACCACAAACCCAACCAACAACCCAAAACAACCCCACCACACACCACACCCACAAACACAACAACA

Sample Output 5

28
42
51
54
57
60
63
64
65
66