31830번 - 알파벳과 쿼리 (Hard)

문제

Easy 버전과 $N,ドル $Q$의 제한을 제외한 문제 차이는 없다.

다음 조건들을 만족하는 부분 문자열을 알파벳 묶음이라고 하자.

• 하나의 동일한 알파벳으로만 문자열이 이루어져 있어야 한다.
• 전체 문자열에서 해당 부분 문자열을 포함한 길이가 더 긴 부분 문자열로 알파벳 묶음을 만들 수 있으면 그 부분 문자열은 알파벳 묶음이 아니다.

예를 들어 "AAABBAAC"와 같은 문자열이 있을 때, 알파벳 묶음은 "AAA", "BB", "AA", "C"로 4개다. 위의 문자열에서 "B", "AC"는 조건을 만족하지 않으므로 알파벳 묶음이 아니다.

영어 알파벳 대문자로만 이루어진 길이가 $N$인 문자열 $S = S_1 S_2 \dots S_N$가 주어질 때, 다음 쿼리를 수행하는 프로그램을 작성하자.

• 1ドル \ l \ r$ : 부분 문자열 $S_l S_{l+1} \dots S_r$에서 알파벳 묶음의 개수를 출력한다.
• 2ドル \ l \ r$ : 부분 문자열 $S_l S_{l+1} \dots S_r$의 모든 알파벳을 각각 알파벳 순서로 다음인 알파벳으로 변경한다. 단, Z인 경우 A로 변경한다.

$S_l S_{l+1} \dots S_r$는 $S$의 $l$번째 알파벳부터 $r$번째 알파벳까지를 모두 순서대로 포함하는 부분 문자열이다.

입력

첫 번째 줄에 문자열의 길이 $N$과 쿼리의 개수 $Q$가 공백으로 구분되어 주어진다. $(3 \leq N, Q \leq 200 \ 000)$

두 번째 줄에 영어 알파벳 대문자로만 이루어진 길이가 $N$인 문자열 $S$가 주어진다.

세 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다. $(1 \leq l \leq r \leq N)$

1ドル$번 쿼리는 한 번 이상 주어진다.

출력

1ドル$번 쿼리에 대한 결괏값을 한 줄에 하나씩 입력으로 주어진 순서대로 출력한다.

제한

힌트