백준 3653 영화 수집 풀이(c++

문제

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

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

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

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

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 상근이가 가지고 있는 영화의 수 n과 보려고 하는 영화의 수 m이 주어진다. (1 ≤ n, m ≤ 100,000) 둘째 줄에는 보려고 하는 영화의 번호가 순서대로 주어진다.

영화의 번호는 1부터 n까지 이며, 가장 처음에 영화가 쌓여진 순서는 1부터 증가하는 순서이다. 가장 위에 있는 영화의 번호는 1이다. 

출력

각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD를 가장 위에 놓는다.

#include <iostream>
#include <algorithm>
#include <map>
#include <cstring>
using namespace std;

int T, N, M;
int tree[200004], iTemp;
map<int, int> m;

void update(int iIndex, int iValue)
{
    while (iIndex < 200004)
    {
        tree[iIndex] += iValue;
        iIndex += (iIndex & -iIndex);
    }
}

int sum(int iIndex)
{
    int iResult = 0;
    while (iIndex > 0)
    {
        iResult += tree[iIndex];
        iIndex -= (iIndex & -iIndex);
    }
    return iResult;
}

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);    cout.tie(NULL);
    cin >> T;

    while (T--)
    {
        cin >> N >> M;
        memset(tree, 0, sizeof(tree));
        m.clear();
        int iUpdate_Idx = 100001;
        for (int i = 1; i <= N; i++) {
            update(i + iUpdate_Idx, 1);
            m[i] = i + iUpdate_Idx;
        }
        for (int i = 0; i < M; ++i)
        {
            cin >> iTemp;
            int idx = m[iTemp];
            cout << sum(idx) - 1 << " ";
            update(idx, -1);
            update(--iUpdate_Idx, 1);
            m[iTemp] = iUpdate_Idx;
        }
        cout << "\n";
    }
    return 0;
}

펜윅트리 이용 풀이