Overview

This problem requires efficiently computing the “number of positions where two adjacent characters are equal” after each update. By observing that only the neighborhood of the changed character is affected, each update can be processed in \(O(1)\).

Analysis

A matching pair is defined as a position \(i\) where \(S_i = S_{i+1}\), and we want to count the number of such positions.

A naive approach of scanning the entire string to count matching pairs after each update costs \(O(N)\) per update and \(O(NQ)\) overall. Given the constraints \(N \le 10^6,\ Q \le 10^5\), this is too slow.

The key observation is that when only one character is changed, at most 2 matching pairs are affected.

• If the changed position is \(i\) (0-indexed), then only:
  • Pair \((i-1, i)\)
  • Pair \((i, i+1)\) can change. All other pairs remain unchanged since their characters are unaffected.

Therefore, we maintain a current matching pair count same and adjust only these 2 pairs upon each update.

For example, when changing the middle character B to A in ... A B C ...:

• Left pair (A,B) goes from mismatch → match, so +1
• Right pair (B,C) changes depending on its original relationship

This differential update allows for efficient processing.

Algorithm

1. For the initial string, examine all adjacent pairs and compute the match count same.
2. For each update \((i, c)\) (convert from 1-indexed input to 0-indexed):
   • Let the old character be old = S[i].
   • If old == c, nothing changes, so same stays the same.
   • If old != c, do the following:
     • If the left neighbor exists (i-1 >= 0):

          - If pair `(i-1, i)` matched before the change, then `same -= 1`
          - If pair `(i-1, i)` will match after the change, then `same += 1`
       

     • If the right neighbor exists (i+1 < N):

          - If pair `(i, i+1)` matched before the change, then `same -= 1`
          - If pair `(i, i+1)` will match after the change, then `same += 1`
       

     • Finally, update S[i] = c.
   • Append the current same to the output.
3. After all updates, output the answers together.

Complexity

• Time complexity: \(O(N + Q)\) (Initial count is \(O(N)\), each update involves a constant number of comparisons at \(O(1)\))
• Space complexity: \(O(N + Q)\) (String array and output buffer)

Implementation Notes

• Store the string as a list for easy in-place updates.

• Since input positions are 1-indexed, convert them in the code with i = int(i_str) - 1.

• When updating, always subtract using “pre-change information” and add using “post-change information”.

• Skipping the differential computation when old == c avoids unnecessary comparisons.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    S = list(input().strip())

    same = 0
    for i in range(N - 1):
        if S[i] == S[i + 1]:
            same += 1

    out = []
    for _ in range(Q):
        i_str, c = input().split()
        i = int(i_str) - 1

        old = S[i]
        if old != c:
            if i - 1 >= 0:
                if S[i - 1] == old:
                    same -= 1
                if S[i - 1] == c:
                    same += 1
            if i + 1 < N:
                if old == S[i + 1]:
                    same -= 1
                if c == S[i + 1]:
                    same += 1
            S[i] = c

        out.append(str(same))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.3-codex.