영화 수집

• 구간 합 쿼리를 이용해서 풀 수 있다.
• 기본 발상은, i번째 위치에 있던 dvd를 맨 앞으로 옮기는 것을, 1번째부터 i-1번째 위치에 있던 dvd의 위치를 뒤로 하나씩 밀고 1번 자리에 그 dvd를 놓는 대신에, 다른 dvd의 위치를 옮기지 않고 그 dvd를 -1번째에 놓는 것으로만 처리해도 상대적 순서는 유지가 된다는 것이다.
• 이렇게 하면, x번 dvd의 포지션을 트래킹하는 것은 O(1)에 가능하다. 대신 x번 dvd가 i번 포지션에 있다는 정보를 알아도, 그 앞에 있는 dvd 갯수를 따로 계산을 통해서 구해야 하는데, 이것을 세그먼트 트리나 펜윅 트리를 사용해서 구간합으로 처리할 수 있다. 트리의 각 노드가 각 포지션에 대응되고 그 포지션에 dvd가 있으면 1, 없으면 0의 값을 갖게 하면, 맨 앞 포지션부터 i-1포지션까지의 구간합이 i번 포지션보다 앞에 있는 dvd의 갯수가 된다.
• 설명을 편하게 하려고 -1번째 포지션에 추가한다고 했지만, 실제 구현은 m+n개의 포지션을 만들고, [m, m+n) 까지 포지션을 1로 채우고 시작한 뒤에, dvd를 맨 앞으로 옮길때마다 m-1, m-2, … 번째 포지션에 추가하면 된다. 트리의 크기는 m+n이다.
• 초기화에 O(m+n)이 들고, m개의 쿼리를 각각 O(log(m+n))에 처리할 수 있으므로, 총 시간 복잡도는 O(n+mlog(m+n)).

"""Solution code for "BOJ 3653. 영화 수집".

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

import sys
from teflib import fenwicktree


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        n, m = [int(x) for x in sys.stdin.readline().split()]
        movie_nums = [int(x) for x in sys.stdin.readline().split()]

        fenwick = fenwicktree.FenwickTree([0] * m + [1] * n)
        pos_by_movie = list(range(m, m + n))
        new_pos = m - 1
        for movie_num in movie_nums:
            cur_pos = pos_by_movie[movie_num - 1]
            print(fenwick.query(0, cur_pos), end=' ')
            fenwick.update(cur_pos, -1)
            fenwick.update(new_pos, 1)
            pos_by_movie[movie_num - 1] = new_pos
            new_pos -= 1
        print()


if __name__ == '__main__':
    main()

• Dependency: teflib.fenwicktree.FenwickTree