서로 다른 수와 쿼리 1

• 구간 내에서 서로 다른 수의 갯수를 찾는 쿼리는 적절한 변환을 통해서 구간 Rank 쿼리 문제로 변환할 수 있다.
• 주어진 수열 A[0:n]에 대응하는 수열 B[0:n]을 만든다. B[i]=x, where A[x] = A[i] and x>i 로 잡는다. 쉽게 말해 i 이후에 처음으로 A[i]값이 다시 등장하는 인덱스를 B[i]로 잡는다. 이렇게 하면 이제 [l:r]구간에서 서로 다른 수의 갯수는 B[i]>r인 수의 갯수이다.
• B[i]를 구하는 것은 O(n)에 계산 가능. B[i]>r인 수의 갯수는 구간 Rank 쿼리에서 설명한 방법대로 오프라인 쿼리를 적용해서 쿼리당 O(logn)에 계산하는 것이 가장 효과적이다.
• 하지만 이렇게 B[i]를 미리 다 구해 놓고서 쿼리를 계산하는 것이 구간 Rank 쿼리를 계산하는 오프라인 쿼리/머지소트 트리/PST에 모두 적용 가능한 방법이긴 했지만, 오프라인 쿼리로 계산한다면 이 방법을 조금 바꿔서 사용하는 것도 가능하다.
• C[0:r] 수열을 만든다. 이 수열은 어떤 값이 [0:r] 범위에서 가장 마지막으로 등장하는 위치에만 1을 갖고, 나머지는 0을 갖는다. [l:r]구간에서 서로 다른 수의 갯수는 C[0:r]수열에서 [l:r]범위에서의 합으로 계산된다. C[0:r+1] 수열로 확장할때에는, C[r]=1로 만들어주고, A[r]이 기존에 마지막으로 나왔던 위치를 찾아서 그곳의 C값을 0으로 바꿔주면 된다.
• 앞선 값을 다시 수정해가면서 풀어야 하기 때문에 오프라인 쿼리나 PST로만 풀수 있지만, 코드 자체는 좀 더 간편하다. 여기에서도 이 방식으로 오프라인 쿼리를 사용해서 풀었다.
• 수열과 쿼리 5와 같은 문제이지만, n과 q의 범위가 10배로 증가했다. python으로 13초 가까이 걸려서 통과된다..
• 서로 다른 수와 쿼리 2는 오프라인 쿼리를 막아놓은 버전이다. PST를 사용하는 풀이는 이쪽을 참고.

"""Solution code for "BOJ 14897. 서로 다른 수와 쿼리 1".

- Problem link: https://www.acmicpc.net/problem/14897
- Solution link: http://www.teferi.net/ps/problems/boj/14897
"""

import sys
from teflib import fenwicktree


def main():
    N = int(sys.stdin.readline())
    A = [int(x) for x in sys.stdin.readline().split()]
    queries = [[] for _ in range(N)]
    Q = int(sys.stdin.readline())
    for query_num in range(Q):
        l, r = [int(x) for x in sys.stdin.readline().split()]
        queries[r - 1].append((l - 1, query_num))

    last_pos = dict()
    fenwick = fenwicktree.FenwickTree(N)
    answers = [None] * Q
    for i, a_i in enumerate(A):
        try:
            fenwick.update(last_pos[a_i], -1)
        except KeyError:
            pass
        fenwick.update(i, 1)
        last_pos[a_i] = i
        for l, query_num in queries[i]:
            answers[query_num] = fenwick.query(l, i + 1)

    print(*answers, sep='\n')


if __name__ == '__main__':
    main()

• Dependency: teflib.fenwicktree.FenwickTree