Overview

Given a bulletin board with \(N\) characters arranged in a row, \(Q\) queries are provided, each replacing a single character. The problem asks to efficiently determine, after each update, how many positions have adjacent characters that are equal (matching pairs).

Observations

The simplest approach is to scan the entire bulletin board after each query to recount the matching pairs. However, this method takes \(O(N)\) time per query, resulting in \(O(NQ)\) overall. Given the constraints \(N \le 10^6, Q \le 10^5\), this would require up to approximately \(10^{11}\) operations, which will not fit within the time limit.

Here, we focus on “how does the total number of matching pairs change when a single character is rewritten?” When the character \(S_i\) at position \(i\) is rewritten, only the following 2 locations are affected in determining matching pairs: - Pair with the left neighbor: \((S_{i-1}, S_i)\) - Pair with the right neighbor: \((S_i, S_{i+1})\)

Pairs at all other positions (e.g., \(S_{i-2}\) and \(S_{i-1}\), etc.) are unaffected since their characters have not changed, so their matching status remains the same. Therefore, for each query, we only need to compute the difference between the “adjacency state before the update” and the “adjacency state after the update” to efficiently update the total count.

Algorithm

1. Initial state computation: First, scan the string \(S\) once to compute the current total number of matching pairs, current_count.
2. Query processing: For each update query \((i, c)\), perform the following operations:
   • Compare the character \(S_i\) before the update with its neighbors (\(S_{i-1}, S_{i+1}\)). If they match, decrement current_count by 1.
   • Replace the character at position \(i\) with \(c\).
   • Compare the character \(S_i\) after the update with its neighbors (\(S_{i-1}, S_{i+1}\)). If they match, increment current_count by 1.
   • However, at the edges of the bulletin board (\(i=1\) or \(i=N\)), skip the check on the side where no neighbor exists.
3. Output the result: Output current_count after each update.

Complexity

• Time complexity: \(O(N + Q)\)
  • The initial count computation takes \(O(N)\), and each query is processed in \(O(1)\) (a constant number of comparisons), so the overall complexity is \(O(N + Q)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for the list that holds the string.

Implementation Notes

• String handling: Python’s string type (str) cannot be modified in place (it is immutable), so by converting it to a list of characters (list), we can update elements at specific indices in \(O(1)\).

• Index adjustment: The problem statement uses 1-indexed (starting from 1) positions, but within the program we need to handle them as 0-indexed (starting from 0), so adjustments such as subtracting -1 when reading input are necessary.

• I/O optimization: Since \(N\) and \(Q\) can be large, using sys.stdin.read() to read all input at once instead of input(), and accumulating results in a list to output with join at the end, can reduce execution time.

  Source Code

import sys

def solve():
    # 標準入力から全てのデータを読み込み、空白文字（スペースや改行）で分割してトークンのリストを作成します。
    # N=10^6, Q=10^5 程度の規模であれば、この方法がPythonにおいて高速な入力読み込み手法の一つです。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 最初のトークンはマスの個数 N、次は更新回数 Q
    N = int(input_data[0])
    Q = int(input_data[1])
    
    # 3番目のトークンは初期状態の文字列 S です。
    # Pythonの文字列はイミュータブル（変更不可）なため、文字の書き換えができるようにリストに変換します。
    S = list(input_data[2])
    
    # 初期状態における「一致ペア」の個数を計算します。
    # 一致ペアとは、隣り合う2つのマスが同じ文字である組 (S[i], S[i+1]) のことです。
    current_count = 0
    for i in range(N - 1):
        if S[i] == S[i+1]:
            current_count += 1
            
    results = []
    
    # Q 回の更新クエリを順番に処理します。
    # 各クエリは (更新位置 i_k, 変更後の文字 c_k) の2つのトークンからなります。
    # クエリの内容は input_data[3] 以降に格納されています。
    for k in range(Q):
        # 位置 i_k は 1-indexed（1から始まる）なので、0-indexed（0から始まる）に変換します。
        idx = int(input_data[3 + 2*k]) - 1
        new_char = input_data[4 + 2*k]
        old_char = S[idx]
        
        # 変更後の文字が現在の文字と異なる場合のみ、一致ペアの個数に影響が出る可能性があります。
        if old_char != new_char:
            # 1. 左隣のマス (idx-1) とのペアを確認
            if idx > 0:
                # 変更前が一致していたなら、カウントを 1 減らす
                if S[idx-1] == old_char:
                    current_count -= 1
                # 変更後に一致するようになるなら、カウントを 1 増やす
                elif S[idx-1] == new_char:
                    current_count += 1
            
            # 2. 右隣のマス (idx+1) とのペアを確認
            if idx < N - 1:
                # 変更前が一致していたなら、カウントを 1 減らす
                if S[idx+1] == old_char:
                    current_count -= 1
                # 変更後に一致するようになるなら、カウントを 1 増やす
                elif S[idx+1] == new_char:
                    current_count += 1
            
            # マスの文字を実際に更新します。
            S[idx] = new_char
            
        # 各更新後のカウントを結果リストに追加します（出力高速化のため文字列として保存）。
        results.append(str(current_count))
        
    # 全てのクエリの結果を改行で連結し、一括で出力します。
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.