BOJ)3653 영화 수집

문제: icpc.me/3653

순서대로 쌓여있는 DVD가 있을 때 영화를 볼때마다 위에 몇개의 DVD가 쌓여있는지 출력하는 문제이다. 이 때 본 영화는 맨위에 쌓는다고 한다.

우리는 세그먼트 트리의 구간합을 통하여 문제를 해결할 수 있다.

우선 n+m+1개의 노드중 m+1~n+m+1에 해당하는 리프에 1씩 업데이트 시킨다. 이는 n개의 DVD가 m+1부터 순서대로 존재한다는 것을 의미한다.

이 때 i번 DVD는 i+m에 존재한다고 기록해 준 뒤 

i번째 영화위의 DVD의 개수는 1~(i번 DVD의 위치-1)의 구간합으로 구해줄 수 있다.

DVD를 뺐으므로 원래 DVD의 위치는 0으로 갱신해 준 후 맨 위에 DVD를 갱신해 줘야한다.

맨위는 i번째 쿼리를 처리할 때 m+1-i 번째 위치일 것이다. 해당 위치를 DVD의 위치로 갱신해 준 뒤 리프에 1을 업데이트 시켜주면 된다. 

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX_N 100000
using namespace std;
int seg[8 * MAX_N], a[2 * MAX_N + 1], t, n, m, v;
int update(int pos, int val, int node, int x, int y) {
    if (y < pos || pos < x)
        return seg[node];
    if (x == y)
        return seg[node] = val;
    int mid = (x + y) >> 1;
    return seg[node] = update(pos, val, node * 2, x, mid) + update(pos, val, node * 2 + 1, mid + 1, y);
}
int query(int lo, int hi, int node, int x, int y) {
    if (y < lo || hi < x)
        return 0;
    if (lo <= x&&y <= hi)
        return seg[node];
    int mid = (x + y) >> 1;
    return query(lo, hi, node * 2, x, mid) + query(lo, hi, node * 2 + 1, mid + 1, y);
}
int main() {
    scanf("%d", &t);
    while (t--) {
        memset(a, 0, sizeof(a));
        memset(seg, 0, sizeof(seg));
        scanf("%d%d", &n, &m);
        int idx = m + 1;
        for (int i = idx; i <= n + m; i++) {
            update(i, 1, 1, 1, n + m);
            a[i - m] = i;
        }
        idx = m;
        for (int i = 0; i < m; i++) {
            scanf("%d", &v);
            printf("%d ", query(1, a[v] - 1, 1, 1, n + m));
            update(a[v], 0, 1, 1, n + m);
            a[v] = idx--;
            update(a[v], 1, 1, 1, n + m);
        }
        printf("\n");
    }
    return 0;
}