[백준] 3653번 영화 수집 C++ 코드

코드

#include <iostream>
#include <vector>
#include <cstring>
#include <map>
#include <cmath>
#include <algorithm>
#include <queue>
#include <string>

using namespace std;
typedef long long ll;
const int MAX_N = 200003;
int t, n, m;
vector<ll> tree;

void update(int idx, int diff) {
    while(idx <= tree.size()) {
        tree[idx] += diff;
        idx += (idx & -idx);
    }
}

ll sum(int idx) {
    ll ans = 0;
    while(idx > 0) {
        ans += tree[idx];
        idx -= (idx & -idx);
    }
    return ans;
}

void FASTIO() {
    ios_base::sync_with_stdio();
    cin.tie(NULL);
    cout.tie(NULL);
}

// 문제에서는 0 0 0 0 0 1, 2, 3, 4, 5 이런 식으로 줬지만
// 거꾸로 생각하니 헷갈려서
// 5 4 3 2 1 0 0 0 0 0 으로 트리를 구성

int main() {
    FASTIO();
    cin >> t;
    while(t--) {
        cin >> n >> m;
        tree.assign(MAX_N, 0);
        int idx = 1;
        map<int,int> mp; // 몇 번째에 있는지 저장할 맵
        for(int i = n; i > 0; i--) {
            update(idx , 1);
            mp[i] = idx;
            idx++;
        }

        for(int i = 0; i < m; i++) {
            int a;
            cin >> a;

            int cnt = sum(idx) - sum(mp[a]); // 사이에 책 있는 개수 찾기
            update(mp[a], -1); // 원래 위치에서 빼주고
            update(idx, 1); // 제일 위에 올려주기
            mp[a] = idx;
            idx++; // 인덱스 증가
            cout << cnt << " ";
        }
        cout << '\n';
    }
    return 0;
}

풀이

펜윅 트리를 이용해서 개수를 저장하고, 업데이트 하여 푼 문제. 문제에서는 0 0 0 0 1 2 3 4 5 이렇게 되어 있어서 거꾸로 해보려다가 너무 헷갈려서 5 4 3 2 1 0 0 0 0 0으로 전환하여 해결하고자 했다. 해당 인덱스 값에 1을 쌓아주고 차이를 이용해서 개수를 세어주었다. resize와 assign의 차이를 알게 된 문제기도 하다.