[BOJ][Python] 백준 3653번 - 영화 수집

문제 링크: https://www.acmicpc.net/problem/3653

---

문제 풀이

세그먼트 트리

 

N+M개의 배열을 생각해서 세그트리를 짜면 된다. 그리고 인덱스 배열을 하나 만들 건데 [0, n, n-1, n-2, ..., 1]로 만들어준다. 그 이유는 1이 가장 위에 있으므로 자신의 위쪽엔 아무것도 없다. 이를 배열로 생각하면 자신의 오른쪽에는 아무것도 없다라는 의미고 아래는 자신의 왼쪽이라고 생각하면 된다. 아무튼 인덱스가 지금 최대 n이니 책을 꺼냈다면 그 책의 인덱스는 이제 n+1이 되고 원래 있었던 인덱스의 세그 값은 0으로, 새롭게 만들어진 인덱스는 1로 업데이트 하면 문제에 대한 쿼리를 적절하게 수행할 수 있다.

 

 

코드

	import sys
	input = sys.stdin.readline
	def init(n):
	for i in range(1, n+1):
	tree[i+n+m] = 1
	for i in range(n+m-1, 0, -1):
	tree[i] = tree[i<<1] + tree[i<<1|1]
	def query(tree, l, r, n):
	l += n
	r += n
	t = 0
	while l < r:
	if l&1:
	t += tree[l]
	l += 1
	if r&1:
	r -= 1
	t += tree[r]
	l >>= 1
	r >>= 1
	return t
	def update(tree, idx, n, val):
	idx += n
	tree[idx] = val
	while idx > 1:
	tree[idx>>1] = tree[idx]+tree[idx^1]
	idx = idx>>1
	for _ in range(int(input())):
	n, m = map(int, input().split())
	tree = [0 for _ in range((n+m)*2+10)]
	arr = list(map(int, input().split()))
	idx = [i for i in range(n+1, 0, -1)]; idx[0] = 0
	init(n)
	now_idx = n+1
	ans = []
	for i in arr:
	ans.append(query(tree, idx[i]+1, n+m+1, n+m))
	update(tree, idx[i], n+m, 0)
	idx[i] = now_idx
	update(tree, idx[i], n+m, 1)
	now_idx += 1
	print(*ans)

view raw 3653.py hosted with ❤ by GitHub