연습문제

[한양대 HCPC 2023] 쿼리는 락이 아니다

난이도
Lv. 5
제출
2 명
참가자
2 명
정답률
100.00 %
지원 언어
C
C++
Java
Python
JavaScript
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
C++ 2초 1024MB
JavaScript 8초 1024MB
C 2초 1024MB
Java 5초 1024MB
Python 8초 1024MB


나락도 락이고, 부모님께 온 연락도 락이고, 오락가락?도 락?이지만?, 아쉽게도 쿼리는 락이 아니다.


알파벳 대문자로 이루어진 길이 N의 문자열 S = s1s2…sN가 주어진다. 이때, 다음과 같은 쿼리를 Q번 처리해야 한다.


-  1 idx c: sidx를 c로 변경한다. (1 ≤ idx ≤ N, c는 알파벳 대문자)


-  2 l r: slsl+1 … sr의 부분열 중 ROCK으로 끝나는 문자열의 개수를 출력한다. 단, 수가 매우 클 수 있으니 109+7로 나눈 나머지를 출력한다. (1 ≤ l ≤ r ≤ N)

제약조건

4 ≤ N ≤ 250,000

문자열 S는 알파벳 대문자로만 이루어져 있다.

1 ≤ Q ≤ 250,000

가장 마지막으로 주어지는 쿼리는 2번 쿼리이다.

입력형식

첫 번째 줄에 문자열 S의 길이 N이 주어진다.

두 번째 줄에 문자열 S가 주어진다.

세 번째 줄에 쿼리의 개수 Q가 주어진다.

네 번째 줄부터 Q개의 줄에 걸쳐 쿼리가 주어진다.

출력형식

 2번 쿼리에 대해 정답을 한 줄에 하나씩 출력한다.

입력예제1

6
NAROCK
3
2 1 6
1 3 C
2 2 5
출력예제1

4
0

입력예제2

6
RRROCK
3
2 3 6
2 2 6
2 1 6
출력예제2

1
3
7

목록