BOJ 3653 영화 수집

문제

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

1~n까지의 영화가 순서대로 쌓여 있을때 i번째 영화 위의 영화의 개수를 출력하고, i번째 영화를 맨 위로 올려놓는 과정을 반복하는 문제이다.

 

풀이

문제 설명 그대로 시뮬레이션을 하면 된다.

N+M개의 칸을 준비해놓고, 영화는 마지막 N개 칸에 모두 넣어 놓은 다음, 하나씩 앞의 칸으로 옮겨 준다.

이때 각 영화 위의 영화 수를 찾아내기 위해서 펜윅 트리의 구간합을 사용한다.

 

시간 복잡도 : $O((N+M)lg(N+M))$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

struct BIT
{
    int n; vector<int> tree;

    BIT(int n) : n(n), tree(n) {}
    int sum(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
    void update(int i, int val) { for(; i<=n; i+=(i&-i)) tree[i]+=val; }
};

int T;
int n, m, pos[MAXN+10];

int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int i, j;

    scanf("%d", &T);

    while(T--)
    {
        scanf("%d%d", &n, &m);
        BIT bit(n+m);
        for(i=1; i<=n; i++) { pos[i]=m+i; bit.update(m+i, 1); }

        for(; m>=1; m--)
        {
            int t;
            scanf("%d", &t);
            printf("%d ", bit.sum(pos[t]-1));
            bit.update(pos[t], -1); bit.update(m, 1);
            pos[t]=m;
        }
        printf("\n");
    }

    return 0;
}