수열과 쿼리 5

• 서로 다른 수와 쿼리 1 과 동일한 문제. 풀이는 그쪽을 참고.
• n, m의 범위 제한이 작아서 Mo's algorithm으로 풀린다는 차이가 있긴 하다

"""Solution code for "BOJ 13547. 수열과 쿼리 5".

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

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)]
    M = int(sys.stdin.readline())
    for query_num in range(M):
        i, j = [int(x) for x in sys.stdin.readline().split()]
        queries[j - 1].append((i - 1, query_num))

    last_pos = dict()
    fenwick = fenwicktree.FenwickTree(N)
    answers = [None] * M
    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