| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 161 | 78 | 66 | 49.624% |
다다스는 물고기를 아주 좋아해서 물고기 화석 하나를 소중히 간직하고 있다. 이 화석은 총 $N$개의 조각으로 이루어져 있으며, 각 조각은 > 또는 < 중 하나의 모양을 갖는다. 모든 조각은 일렬로 나열되어 있으며, 각 조각은 왼쪽에서부터 1,ドル 2, \cdots, N$번 조각이다.
모그는 다다스가 정말로 물고기를 좋아하는지를 확인해보기 위해 총 $Q$번의 행동을 취한다. 각 행동은 다음 두 가지 중 하나이다:
1 l r: $l \leq i \leq r$를 만족하는 모든 정수 $i$에 대해 $i$번째 조각을 각각 180도 회전시킨다. 즉 >는 <로, <는 >로 바뀐다.2: 현재 화석에서 물고기의 개수를 출력한다. 물고기란, 연속된 세 조각이 ><> 또는 <>< 형태를 갖는 경우를 말한다.다다스는 계산에 약하므로 여러분이 대신해서 모그의 행동을 처리해주어야 한다. 모그의 모든 행동에 올바르게 응답하자.
첫 번째 줄에 양의 정수 $N$이 주어진다. (1ドル\le N\le 3\times10^5$)
두 번째 줄에 물고기 화석을 이루는 $N$개의 조각이 공백 없이 주어진다. 각 조각은 >또는 <중 하나이다.
세 번째 줄에 양의 정수 $Q$가 주어진다. (1ドル\le Q\le 3\times10^5$)
네 번째 줄부터 $Q$개의 줄에 걸쳐 1번 또는 2번 쿼리가 주어진다. 2번 쿼리는 최소 한 개 이상 주어진다. (1ドル\le l\le r\le N$)
2번 쿼리가 주어질 때마다 물고기 화석에서의 물고기의 개수를 출력하여라.
6 ><>><> 6 2 1 4 6 2 1 1 2 1 2 3 2
2 4 1
다음은 예제의 초기 물고기 화석 그림이다.
첫 번째 행동인 2에 대해서는 다음과 같이 물고기가 2개 있으므로, 첫 번째 줄에 2ドル$를 출력해야 한다.
두 번째 행동인 1 4 6은 4번부터 6번 조각을 각각 180도 회전시키는 작업이며, 그 결과 화석은 다음과 같이 변한다.
세 번째 행동인 2에 대해서는 다음과 같이 물고기가 4개 있으므로, 두 번째 줄에 4ドル$를 출력해야 한다.