Alphabet Queries (Hard)

This version differs from the Easy version only in the limits of $N$ and $Q$.

A substring that satisfies both conditions below is called a letter block.

• It consists of one repeated letter only.
• If a longer substring of the whole string that contains it can form a letter block, then it is not a letter block.

For example, in the string AAABBAAC, the letter blocks are AAA, BB, AA, and C, four in total. In the same string, B and AC do not satisfy the conditions, so they are not letter blocks.

You are given a string $S = S_1 S_2 \dots S_N$ of length $N$ made only of uppercase English letters. Write a program that handles the following queries.

• 1 l r: Print the number of letter blocks in the substring $S_l S_{l+1} \dots S_r$.
• 2 l r: Change every letter in the substring $S_l S_{l+1} \dots S_r$ to the next letter in alphabetical order. Z becomes A.

The substring $S_l S_{l+1} \dots S_r$ contains all characters from position $l$ through position $r$ of $S$, in order.

The first line contains the string length $N$ and the number of queries $Q$, separated by a space. $(3 \leq N, Q \leq 200 \ 000)$

The second line contains the string $S$ of length $N$, made only of uppercase English letters.

Each of the next $Q$ lines contains one query. $(1 \leq l \leq r \leq N)$

At least one query of type $1$ is given.

For each query of type $1$, print the result on its own line, in the order the queries are given.