[백준/13547] 수열과 쿼리 5 (Python)

Problem : https://www.acmicpc.net/problem/13547

13547번: 수열과 쿼리 5

 

Difficulty : Platinum 2

 

Status : Solved

 

Time : 00:51:26

 

---

 

문제 설명

 

 

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

i j: Ai, Ai+1, ..., Aj에 존재하는 서로 다른 수의 개수를 출력한다.

 

 

입력 및 출력

 

입력

 

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다.
둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 1,000,000)
셋째 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.
넷째 줄부터 M개의 줄에는 쿼리 i, j가 한 줄에 하나씩 주어진다. (1 ≤ i ≤ j ≤ N)

 

출력

 

각각의 쿼리마다 정답을 한 줄에 하나씩 출력한다.

 

입력 예시

 

5
1 1 2 1 3
3
1 5
2 4
3 5

 

출력 예시

 

3
2
3

 

 

---

 

풀이

 

Mo's 알고리즘을 이용해 풀어볼 수 있겠다. 이 알고리즘의 핵심은 간단한데, 작은 쿼리 영역부터 큰 쿼리 영역까지 서로 겹친다면, 겹치는 부분을 최대화하는 순으로 쿼리 결과를 생성하는 알고리즘이다. 특성상 쿼리의 순서를 조작해야 하므로 오프라인 쿼리가 필요하다. 여기에 쿼리의 순서를 (l, r)로 두었을 때, (l // sqrt(N), r)순으로 정렬을 하는 sqrt decomposition을 수행할 수 있다.

 

총 쿼리의 수를 M이라 두자.

 

• l은 이전 쿼리에서 다음 쿼리간 총 O(sqrt(N))번 움직이게 된다(같은 버킷이라면 당연히 sqrt(N) 거리 내이고, 다른 버킷이라도 인접하였으므로 sqrt(N)의 배수 개수만큼 움직입니다). 즉 모든 쿼리에 대해서 O(Msqrt(N)) 의 시간복잡도로 움직인다.
• r은 같은 sqrt(N) 버킷 내에서 오름차순으로 증가하는 형태를 띄고, 이 sqrt(N) 버킷은 총 sqrt(N)개 존재한다. 즉 모든 쿼리에 대해서 O(Nsqrt(N))의 시간복잡도로 움직인다.

따라서 총 시간복잡도는 O((M+N)sqrt(N))이 소요된다.

 

풀이 코드

from collections import defaultdict
import sys
input = sys.stdin.readline

N = int(input())
sqrt = N ** 0.5
nums = list(map(int, input().split()))
M = int(input())
ans = [0]*M

queries = [[i] + list(map(int, input().split())) for i in range(M)]
queries.sort(key = lambda x : (x[1] // sqrt, x[2]))

num_list = defaultdict(int)
cnt, prev_i, prev_j = 0, 0, -1

for idx, i, j in queries :
  i -= 1
  j -= 1
  while prev_j < j :
    prev_j += 1
    if not num_list[nums[prev_j]] :
      cnt += 1
    num_list[nums[prev_j]] += 1
  while prev_j > j :
    num_list[nums[prev_j]] -= 1
    if not num_list[nums[prev_j]] :
      cnt -= 1
    prev_j -= 1
  while prev_i < i :
    num_list[nums[prev_i]] -= 1
    if not num_list[nums[prev_i]] :
      cnt -= 1
    prev_i += 1
  while prev_i > i :
    prev_i -= 1
    if not num_list[nums[prev_i]] :
      cnt += 1
    num_list[nums[prev_i]] += 1
  ans[idx] = cnt
print(*ans, sep = '\n')

풀이 완료!