31222번 - 수열과 어렵지 않은 쿼리 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 300 | 215 | 192 | 75.000% |
문제
백준 온라인 저지에는 많은 "수열과 쿼리" 문제가 있습니다. 그러나 그중 대다수는 Diamond 이상의 티어를 가지고 있기에, 흐즈로는 언젠가는 어렵지 않은 "수열과 쿼리" 문제를 내겠다고 다짐하였습니다. 그렇게 탄생한 문제가 이것입니다.
수열의 연속 부분 수열 $[a_l,a_{l+1},a_{l+2},\cdots,a_{r-1},a_r]$에서 모든 원소가 서로 일치할 때, 이러한 구간 $[l,r]$을 수열 $a$의 연속 일치 구간이라고 합니다. 또한, 수열 $a$의 어떤 연속 일치 구간이 다른 어떤 $a$의 연속 일치 구간에도 완전히 포함되지 않는다면 이를 수열 $a$의 중요한 연속 일치 구간이라고 합니다.
여러분은 인덱스가 $1$부터 시작하는 수열 $A$에 대하여 다음의 쿼리 $q$개를 해결해야 합니다.
- $1 \ i \ x$: $A_i$의 값을 $x$로 변경합니다. ($1 \le i,x \le n$)
- $2 \ l \ r$: $B$를 수열의 연속 부분 수열 $[A_l,A_{l+1},A_{l+2},\cdots,A_{r-1},A_r]$로 정의할 때, 수열 $B$의 서로 다른 중요한 연속 일치 구간의 개수를 출력합니다. ($1 \le l \le r \le n$)
어렵지 않은 문제죠? 여러분이 느끼기에도 어렵지 않다면 좋겠습니다.
입력
첫 번째 줄에 수열의 길이 $n$과 쿼리의 개수 $q$가 공백으로 분리되어 주어집니다. ($1 \le n,q \le 2\times 10^5$)
두 번째 줄에 수열 $A$의 원소 $A_1, A_2, \cdots, A_n$이 공백으로 분리되어 주어집니다. ($1 \le A_i \le n$)
그다음 줄부터 총 $q$개의 쿼리가 한 줄에 하나씩 주어집니다. 각 쿼리는 지문에 주어진 종류의 쿼리 중 하나입니다.
모든 입력에서 마지막 쿼리는 $2$번 쿼리임이 보장됩니다.
출력
각 $2$번 쿼리에 대해 정답을 한 줄에 하나씩 출력합니다.
예제 입력 1
10 9 1 1 1 2 2 1 1 4 4 4 2 1 10 2 2 6 2 2 5 1 2 7 2 1 10 2 2 6 2 7 8 1 7 4 2 7 8
예제 출력 1
4 3 2 6 4 2 1
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호