Funcia
Lv.4fenwick-treemo-algorithmoffline-queries

구간 안의 서로 다른 값

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

정수 배열 a와 질의 목록 queries가 주어집니다. 각 질의 queries[k] = [l, r]에 대해 구간 a[l], a[l+1], ..., a[r]에 들어 있는 서로 다른 값의 개수를 구해, 질의 순서대로 배열에 담아 반환하세요.

인덱스는 0부터 시작하며, l과 r은 모두 구간에 포함됩니다.

입출력 예

aqueriesresult
[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[]

제한 사항

  • 1≤N=1 \le N = a.length ≤200,000\le 200{,}000
  • −109≤-10^9 \le a[i] ≤109\le 10^9
  • 1≤1 \le queries.length ≤200,000\le 200{,}000
  • queries[k] = [l, r], 0≤l≤r<N0 \le l \le r < N

기대 복잡도

시간
O((N + Q) log N)
공간
O(N + Q)

입출력 예

aqueries기대 출력
[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]

힌트

힌트

질의마다 구간을 훑으면 O(NQ)O(NQ)입니다. 질의를 모아서(오프라인) 유리한 순서로 처리해 보세요.

방법 1 — 오른쪽 끝 기준 스윕 + 펜윅 트리

질의를 r 순서로 처리합니다. r까지 보았을 때, 각 값은 가장 마지막으로 등장한 위치에만 1을 둡니다.

  • a[r]을 볼 때, 같은 값이 이전 위치 p에 있었다면 p의 1을 지우고 r에 1을 놓습니다.
  • 그러면 [l, r]의 서로 다른 값 개수 = 위치 l..r에 놓인 1의 합입니다. 펜윅 트리로 O(log⁡N)O(\log N)에 구합니다.

전체 O((N+Q)log⁡N)O((N + Q) \log N)입니다.

방법 2 — Mo's 알고리즘

구간을 N\sqrt{N} 크기 블록으로 나눠 질의를 정렬한 뒤, 양 끝을 한 칸씩 옮기며 값별 개수를 관리합니다. O((N+Q)N)O((N + Q)\sqrt{N})입니다.

복잡도 목표

질의마다 구간을 직접 세는 풀이는 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)286 ms추정
C++ (GCC, gnu++23)286 ms도출됨
Python 3.131304 ms도출됨
Java 252482 ms도출됨
Kotlin 2.4 (JVM)1572 ms추정
C# 14 (.NET 10)1572 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample02입력·출력 공개
correctness4011판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.