[백준] 3653 영화 수집

문제 링크

http://icpc.me/3653

3653번: 영화 수집

풀이

세그먼트 트리를 이용하여 풀 수 있다.

빼야 하는 dvd를 기준으로 위에 있는 dvd를 모두 세는 연산과 dvd를 하나 빼는 연산을 세그먼트 트리를 이용하여 할 수 있다.

이때 빼고 맨 위에 놓는 연산을 그냥 한다면 O(N)이 들기 때문에 배열을 M+N사이즈로 활용하여 아무것도 없는 곳은 0으로 dvd가 있는 곳은 1로 만들어 사용하며 특정 dvd의 인덱스는 따로 관리한다.

그렇기 때문에 dvd가 있는 총 개수는 구간 합으로 구할 수 있다. 

코드

#include <bits/stdc++.h>
using namespace std;
#define mid ((s + e) >> 1)
const int N = 2e5 + 5;

int tree[4 * N];
int idx[N];

void update(int idx, int k, int node = 1, int s = 0, int e = N) {
    if (e < idx || idx < s) return;
    tree[node] += k;
    if (s == e) return;
    update(idx, k, 2 * node, s, mid);
    update(idx, k, 2 * node + 1, mid + 1, e);
}

int query(int qs, int qe, int node = 1, int s = 0, int e = N) {
    if (e < qs || qe < s) return 0;
    if (qs <= s && e <= qe) return tree[node];
    return query(qs, qe, 2 * node, s, mid) + query(qs, qe, 2 * node + 1, mid + 1, e);
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int t; cin >> t;
    while (t--) {
        memset(tree, 0, sizeof tree);
        int n, m; cin >> n >> m;
        int last = n + 1;
        for (int i = 1; i <= n; i++) {
            update(i, 1);
            idx[i] = n - i + 1;
        }
        for (int i = 0; i < m; i++) {
            int inp; cin >> inp;
            int &k = idx[inp];
            update(k, -1);
            printf("%d ", query(k, last++));
            update(last, 1);
            k = last;
        }
        printf("\n");
    }
}