Lv.4fenwick-treemo-algorithmoffline-queries
구간 안의 서로 다른 값
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
정수 배열 a와 질의 목록 queries가 주어집니다. 각 질의 queries[k] = [l, r]에 대해 구간 a[l], a[l+1], ..., a[r]에 들어 있는 서로 다른 값의 개수를 구해, 질의 순서대로 배열에 담아 반환하세요.
인덱스는 0부터 시작하며, l과 r은 모두 구간에 포함됩니다.
입출력 예
| a | queries | result |
|---|---|---|
[1, 2, 1, 3, 2] | [[0, 4], [0, 2], [1, 1], [2, 3]] | [3, 2, 1, 2] |
[7, 7, 7] | [[0, 2], [1, 2]] | [1, 1] |
입출력 예 설명
예 1
[0, 4]— 구간[1, 2, 1, 3, 2]의 서로 다른 값은1, 2, 3세 개입니다.[0, 2]—[1, 2, 1]에는1, 2두 개가 있습니다.[1, 1]— 원소가 하나뿐이므로1입니다.[2, 3]—[1, 3]에는 두 개가 있습니다.
예 2 — 모든 값이 같으므로 어떤 구간이든 답은 1입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(a: int[], queries: int[][]) → int[]
제한 사항
-
a.length -
a[i] -
queries.length queries[k] = [l, r],
기대 복잡도
- 시간
- O((N + Q) log N)
- 공간
- O(N + Q)
입출력 예
| a | queries | 기대 출력 |
|---|---|---|
[1,2,1,3,2] | [[0,4],[0,2],[1,1],[2,3]] | [3,2,1,2] |
[7,7,7] | [[0,2],[1,2]] | [1,1] |
힌트
힌트
질의마다 구간을 훑으면 입니다. 질의를 모아서(오프라인) 유리한 순서로 처리해 보세요.
방법 1 — 오른쪽 끝 기준 스윕 + 펜윅 트리
질의를 r 순서로 처리합니다. r까지 보았을 때, 각 값은 가장 마지막으로 등장한 위치에만 1을 둡니다.
a[r]을 볼 때, 같은 값이 이전 위치p에 있었다면p의1을 지우고r에1을 놓습니다.- 그러면
[l, r]의 서로 다른 값 개수 = 위치l..r에 놓인1의 합입니다. 펜윅 트리로 에 구합니다.
전체 입니다.
방법 2 — Mo's 알고리즘
구간을 크기 블록으로 나눠 질의를 정렬한 뒤, 양 끝을 한 칸씩 옮기며 값별 개수를 관리합니다. 입니다.
복잡도 목표
질의마다 구간을 직접 세는 풀이는 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 286 ms | 추정 |
| C++ (GCC, gnu++23) | 286 ms | 도출됨 |
| Python 3.13 | 1304 ms | 도출됨 |
| Java 25 | 2482 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1572 ms | 추정 |
| C# 14 (.NET 10) | 1572 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 2 | 입력·출력 공개 |
| correctness | 40 | 11 | 판정만 |
| performance | 60 | 4 | 판정만 |