개발자 크루
남양연구소입니다.
Lv. 5
[한양대 HCPC 2023] 쿼리는 락이 아니다
- 난이도
- 5 단계
- 참가자
- 0 명
- 제출
- 0 명
- 정답률
- 0.00 %
언어별 시간/메모리
| 언어 | 시간 | 메모리 |
|---|---|---|
| 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