영화 수집 (백준 3653)

안녕하세요. 오늘은 영화를 수집할 거예요.

문제

https://www.acmicpc.net/problem/3653

아이디어

세그먼트 트리를 잘 써야합니다.
num[x]를 x번째 DVD가 몇번째 위치에 있는지라고 정의합시다.
맨 처음에 num[1]은 N, num[2]는 N-1 ... num[N]은 1입니다. 여기서 한번 꺼내고 다시 올릴때마다 N+1의 위치로, N+2의 위치로... N+M의 위치로 올리게 됩니다. 그러면 출력을 할 때 자신보다 위, 즉 num[x]+1부터 N+M까지의 합을 출력해주면 됩니다.

소스코드

#include <iostream>
using namespace std;

int N, M;
int tree[808080] = { 0 };
int init(int s, int e, int node)
{
    if (s == e) return tree[node] = (s <= N); //1~N인 경우에만 1 저장 아니면 0 저장
    int mid = (s + e) / 2;
    return tree[node] = init(s, mid, node * 2) + init(mid + 1, e, node * 2 + 1);
}
void change(int s, int e, int node, int idx, int num)
{
    if (idx < s || e < idx) return;
    tree[node] += num;
    if (s == e) return;

    int mid = (s + e) / 2;
    change(s, mid, node * 2, idx, num);
    change(mid + 1, e, node * 2 + 1, idx, num);
}
int SUM(int s, int e, int node, int l, int r)
{
    if (e < l || r < s) return 0;
    if (l <= s && e <= r) return tree[node];

    int mid = (s + e) / 2;
    return SUM(s, mid, node * 2, l, r) + SUM(mid + 1, e, node * 2 + 1, l, r);
}

int NUM[101010] = { 0 };
int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int T;
    cin >> T;
    while (T--)
    {
        cin >> N >> M;
        init(1, N + M, 1);
        for (int i = 1; i <= N; i++) NUM[i] = N - i + 1;
        for (int i = 0; i < M; i++)
        {
            int x;
            cin >> x;
            cout << SUM(1, N + M, 1, NUM[x] + 1, N + M) << ' '; //합 (위에 있는 개수) 출력
            change(1, N + M, 1, NUM[x], -1); //그 자리에는 없애고
            change(1, N + M, 1, N + i + 1, 1); //새로운 자리에 추가
            NUM[x] = N + i + 1; //위치도 변경
        }
        cout << "\n";
    }
}

감사합니다.