영화 수집 - 3653

//3653 - 영화 수집
 
#include <iostream>
#include <vector>
using namespace std;
 
int N, M;
int idx[100001];
 
struct FenwickTree
{
    vector<int> tree;
 
    FenwickTree(int n) : tree(n, 0) {}
 
    int sum(int pos)
    {
        int ret = 0;
        while(pos > 0)
        {
            ret += tree[pos];
            pos &= (pos-1);
        }
        return ret;
    }
 
    void add(int pos, int val)
    {
        while(pos <= N+M)
        {
            tree[pos] += val;
            pos += (pos & -pos);
        }
    }
};
 
void init()
{
    cin >> N >> M;
    for(int i = 1; i<=N; ++i)
        idx[i] = M+i;
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);                            
    int C; cin >> C;
    for(int tn = 0; tn<C; ++tn)
    {
        init();
        FenwickTree fwt(N+M+1);
        for(int i = 1; i<=N; ++i)
            fwt.add(idx[i], 1);
        int u;
        int to = M;
        for(int i = 0; i<M; ++i)
        {
            cin >> u;
            int from = idx[u];
            cout << fwt.sum(from-1) << " ";
            fwt.add(from, -1);
            idx[u] = to;
            fwt.add(to--, 1);
        }
        cout << "\n";
    }
}

 

 

 

 

 

 

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

3653번: 영화 수집

 

 

 

 

 

 

영화 수집

일자로 쭉 서있는 원소들 중에서 하나를 선택해 그 앞에 있는 원소의 수를 출력하고, 해당 원소를 맨 앞으로 보내는 과정을 반복합니다.

원소의 수 만큼 선형 자료구조를 만들어 위 작업을 반복하면, 원소들의 위치를 조정하는 과정에서 시간초과가 발생합니다.

원소들의 위치를 조정하는 작업 없이 똑같은 효과를 내어야 하는데, 굳이 빈 자리를 매꾸지 않으면 됩니다.

이를위해 선형자료구조를 N+M크기로 잡아주고, 초기에 M+1 .... M+N 위치에 원소들을 자리시킨다음, 앞으로 이동해야 하는 원소만 순서대로 M, M-1, M-2... 위치로 이동시키고 부분합을 구하게 되면 원소들의 위치를 조정하는 과정 없이 똑같은 효과를 낼수 있습니다.

부분합을 구하는 방법은 펜윅트리를 사용하면 빠르게 구할 수 있기 때문에 시간초과 없이 문제를 해결할 수 있습니다.

(펜윅트리의 sum, add 는 lgn만큼의 시간복잡도를 가집니다. 따라서 총 nlgn만에 해결할 수 있습니다.)