Overview

In a single update, the matching pairs that can potentially change are at most the 2 pairs to the left and right of the updated cell.
Using this property, by updating the total count of matching pairs in \(O(1)\) each time, we can process the entire problem efficiently.

Analysis

A matching pair refers to a pair of adjacent cells that have the same character.
In other words, for \(1 \le i < N\), if \(S_i = S_{i+1}\), then that \(i\) constitutes one matching pair.

Key Insight

When only one cell’s character is changed, the only affected pairs are the adjacent pairs that include that cell.

When changing the character at position \(pos\), only the following 2 pairs can potentially change:

• \((pos-1, pos)\)
• \((pos, pos+1)\)

All other pairs remain completely unchanged in their two characters, so their match/mismatch status stays the same.

Why the Naive Approach Is Slow

If we scan the entire string and recount the number of matching pairs after each update, it takes \(O(N)\).
Doing this \(Q\) times gives an overall complexity of \(O(NQ)\).

The constraints are:

• \(N \le 10^6\)
• \(Q \le 10^5\)

So in the worst case, this results in about \(10^{11}\) operations, which is too slow.

How to Solve It

We count the number of matching pairs in the entire string just once at the beginning.
Then for each subsequent update, we only look at the 2 affected pairs and adjust the count.

Specifically, when updating position \(pos\):

1. Before the change:
   • If \((pos-1, pos)\) was a match, decrease the count by 1
   • If \((pos, pos+1)\) was a match, decrease the count by 1
2. Actually change the character
3. After the change:
   • If \((pos-1, pos)\) is now a match, increase the count by 1
   • If \((pos, pos+1)\) is now a match, increase the count by 1

This way, there is no need to rescan the entire string each time.

Concrete Example

For example, when \(S=\texttt{AABBA}\), the matching pairs are:

• \((1,2)\): A and A — match
• \((2,3)\): A and B — no match
• \((3,4)\): B and B — match
• \((4,5)\): B and A — no match

So the count is 2.

Now, if we change the 3rd character to A, the affected pairs are:

• \((2,3)\)
• \((3,4)\)

only.

Before the change: - \((2,3)\) is not a match - \((3,4)\) is a match → decrease by 1

After the change, the string is AAABA, so: - \((2,3)\) is a match → increase by 1 - \((3,4)\) is not a match

As a result, the count remains 2.

Algorithm

1. Examine all adjacent pairs in string \(S\) to compute the initial matching pair count cnt.
2. For each update, let the update position be \(pos\) (convert to 0-indexed in the implementation).
3. Before the update, check the following (if they exist) and subtract from cnt:
   • \(S_{pos-1} = S_{pos}\)
   • \(S_{pos} = S_{pos+1}\)
4. Change \(S_{pos}\) to the new character.
5. After the update, check the following (if they exist) and add to cnt:
   • \(S_{pos-1} = S_{pos}\)
   • \(S_{pos} = S_{pos+1}\)
6. Output the current value of cnt.

With this method, each update only examines at most 2 pairs, making it fast.

Complexity

• Time complexity: \(O(N + Q)\)
• Space complexity: \(O(N + Q)\)

Implementation Notes

• The input position \(i_k\) is 1-indexed, so in the implementation we convert it to 0-indexed with pos = i_k - 1.

• At the endpoints, some adjacent pairs don’t exist, so we check:

  • Left side: pos > 0
  • Right side: pos < n - 1
    before making comparisons.

• Since Python strings are immutable, the code uses bytearray to efficiently perform single-character updates.

• Although we could print the answer after each update, this code accumulates results in ans and outputs them all at once at the end.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    q = int(data[1])
    s = bytearray(data[2])

    cnt = 0
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            cnt += 1

    ans = []
    idx = 3
    for _ in range(q):
        pos = int(data[idx]) - 1
        c = data[idx + 1][0]
        idx += 2

        if pos > 0 and s[pos - 1] == s[pos]:
            cnt -= 1
        if pos < n - 1 and s[pos] == s[pos + 1]:
            cnt -= 1

        s[pos] = c

        if pos > 0 and s[pos - 1] == s[pos]:
            cnt += 1
        if pos < n - 1 and s[pos] == s[pos + 1]:
            cnt += 1

        ans.append(str(cnt))

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

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.