[BOJ] #3653 영화 수집

시간 제한	메모리 제한	정답 비율
1 초	256 MB	43.106%

3653번: 영화 수집

 

문제

상근이는 영화 DVD 수집가이다. 상근이는 그의 DVD 콜렉션을 쌓아 보관한다.

보고 싶은 영화가 있을 때는, DVD의 위치를 찾은 다음 쌓아놓은 콜렉션이 무너지지 않게 조심스럽게 DVD를 뺀다. 영화를 다 본 이후에는 가장 위에 놓는다.

상근이는 DVD가 매우 많기 때문에, 영화의 위치를 찾는데 시간이 너무 오래 걸린다. 각 DVD의 위치는, 찾으려는 DVD의 위에 있는 영화의 개수만 알면 쉽게 구할 수 있다. 각 영화는 DVD 표지에 붙어있는 숫자로 쉽게 구별할 수 있다.

각 영화의 위치를 기록하는 프로그램을 작성하시오. 상근이가 영화를 한 편 볼 때마다 그 DVD의 위에 몇 개의 DVD가 있었는지를 구해야 한다.

 

해결

key point, 세그먼트 트리, DVD 위치는 바뀌어도, 번호는 바뀌지 않음

• 다른 세그먼트 트리 문제와 형태는 비슷하지만 DVD 위치가 계속해서 바뀌기 때문에, 위치를 기억해줄 배열이 필요하다 → idx[i]
• idx[i]는 i번 DVD의 위치이다. 엄밀히 말하면 세그먼트 트리에서의 위치이다.
  • idx[i]가 1이라면, 세그먼트 트리에서는 h번 노드에 있는 것이고, idx[i]가 6이라면 세그먼트 트리에서는 h + 6번 노드에 있다.
  • idx[i]값이 1일 때 맨 아래 깔려 있는 DVD이고, top이 맨 위에 존재하는 DVD이다.
• 세그먼트 트리의 값을 DVD가 위치하면 1, 없으면 0으로 두어 구간 합으로 i번 DVD 위에 몇 개의 DVD가 있는지 구할 수 있다.
  • i번 영화를 보고 싶다면, i번 영화는 idx[i]에 있기 때문에 그 위에 존재하는 DVD의 개수를 구하기 위해서는
  • idx[i] + 1부터, top까지 구간 합으로 구할 수 있다.

 

코드

메모리	시간
6368 KB	224 ms

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int ll;
vector<ll>seg;
int idx[200005];
int t, n, m, top;
int h = 1;
void update(int i, int val) {
    i += h - 1;
    seg[i] = val;
    while (i > 1) {
        i /= 2;
        seg[i] = seg[i * 2] + seg[i * 2 + 1];
    }
}
ll query(int l, int r, int num, int nl, int nr) {
    if (l <= nl && nr <= r) return seg[num];
    else if (nl > r || nr < l) return 0;
    int mid = (nl + nr) / 2;
    return query(l, r, num * 2, nl, mid) + query(l, r, num * 2 + 1, mid + 1, nr);
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &m);
        while (h < n + m) h <<= 1; //높이구하기 1 2 4 8
        seg.resize(h * 2);
        for (int i = 0; i < n; i++) {
            update(i + 1, 1);
        }
        for (int i = 1, j = 0; i <= n; i++, j++) {
            idx[i] = n - j;
        }
        top = n;
        for (int i = 0, a; i < m; i++) {
            scanf("%d", &a);
            printf("%lld ", query(idx[a] + 1, top, 1, 1, h));
            update(idx[a], 0);
            idx[a] = ++top;
            update(idx[a], 1);
        }
        puts("");
        seg.clear();
        memset(idx, 0, sizeof(idx));
    }
    return 0;
}