8073 : 구간 서로 다른 수
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
길이가 $N$인 수열과 $Q$개의 구간 쿼리가 주어집니다.
각 쿼리 $[l, r]$에 대하여 해당 구간에 포함된 수 중 서로 다른 수의 개수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N, Q \le 30{,}000$
• $1 \le A_i \le 10^6$
• $1 \le l \le r \le N$
각 쿼리 $[l, r]$에 대하여 해당 구간에 포함된 수 중 서로 다른 수의 개수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N, Q \le 30{,}000$
• $1 \le A_i \le 10^6$
• $1 \le l \le r \le N$
입력 설명
첫째 줄에 수열의 크기 $N$과 쿼리의 수 $Q$가 공백으로 구분되어 주어집니다. ($1 \le N, Q \le 30{,}000$)
둘째 줄에 수열을 구성하는 $N$개의 정수가 공백으로 구분되어 주어집니다. ($1 \le A_i \le 10^6$)
셋째 줄부터 $Q$개의 줄에 걸쳐 각 구간 쿼리의 왼쪽 끝 $l$과 오른쪽 끝 $r$이 공백으로 구분되어 주어집니다. ($1 \le l \le r \le N$)
둘째 줄에 수열을 구성하는 $N$개의 정수가 공백으로 구분되어 주어집니다. ($1 \le A_i \le 10^6$)
셋째 줄부터 $Q$개의 줄에 걸쳐 각 구간 쿼리의 왼쪽 끝 $l$과 오른쪽 끝 $r$이 공백으로 구분되어 주어집니다. ($1 \le l \le r \le N$)
출력 설명
각 쿼리에 대해 구간 $[l, r]$ 안의 서로 다른 수의 개수를 한 줄에 하나씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 3
1 2 1 3 2
1 3
2 5
1 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2
3
3도움
Mo's Algorithm(모 알고리즘)을 사용하면 $O((N + Q)\sqrt{N})$에 해결할 수 있습니다.
쿼리를 블록 크기 $\sqrt{N}$ 단위로 정렬한 뒤, 포인터 $l, r$을 이동시키며 현재 구간의 서로 다른 수의 개수를 $O(1)$에 갱신합니다.
쿼리를 블록 크기 $\sqrt{N}$ 단위로 정렬한 뒤, 포인터 $l, r$을 이동시키며 현재 구간의 서로 다른 수의 개수를 $O(1)$에 갱신합니다.