[BOJ 3653] 영화 수집

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

세그먼트 트리로 풀 수 있는 문제다. 하지만 나는 간결한게 좋으므로 펜윅트리로 풀었다!

1. 접근

'm개의 보고싶은 dvd가 있고, dvd를 볼때마다 맨 위로 쌓아놓는다.'

매 번 n개의 배열의 위치를 갱신하여 풀게되면 O(nm) 의 시간복잡도를 나타내게 된다.

n, m <= 100,000 이므로 시간초과가 발생할 수 밖에 없다.

따라서 다른 방법을 찾아보아야 한다.

---

2. 풀이

각 인덱스에, dvd가 존재한다면 1. 존재하지 않는다면 0 을 a[i] 배열에 저장하여 나타내고, 각 인덱스까지의 부분합을 psum이라는 값으로 나타내보자.

다음 표와 같이 상태를 표현할 수 있다.

i	1	2	3	4
a[i]	1	1	1	1
psum	0	1	2	3

3번 dvd의 위치는 3번 dvd보다 위에있는 dvd 갯수가 2개이므로 2이다.
이 때, 1번과 2번이 존재하므로 위치가 2라는 것을 알 수 있다.

그러므로 i번째 dvd의 위치를 알기 위해서 필요한 것은 i보다 작은 인덱스가 몇개 존재하는지, 즉 -∞부터 i까지의 존재 여부의 구간 합 이라고 생각할 수 있다. 구간합을 구하는 문제이므로 펜윅트리를 이용해 풀 수 있다.

DVD는 다 본 뒤 맨 위에 올려놓는다.

한번 본 dvd는 맨 위로 올라가게 되는데, 이 올라간 dvd의 존재 여부도 카운팅이 되어야 제대로 된 정답을 도출할 수 있다. -∞부터 i까지의 구간합을 앞서 위치로 정의하였다. 보고 난 뒤의 올라간 dvd들은 -∞에 위치하면 되는 것이다.

m개의 보고싶은 dvd가 있으므로, 초기의 1번 dvd위에 올라가는 dvd의 갯수는 최대 m개이다.

n = 3, m = 3의 경우

i	0	1	2	3	4	5
a[i]	0	0	0	1	1	1
2번 시청 뒤 a[i]	0	0	1	1	0	1
3번 시청 뒤 a[i]	0	1	1	1	0	0

m = 3 이므로 i = 0, 1, 2 는 한 번 이상 본 dvd들이 존재하는 위치이다.

이 때 조심해야 할 점은, dvd를 한 번 보고 나면, 그 dvd의 원래의 위치가 새로운 위치로 변한다는 점이다.

그래서 추가적인 배열 pos를 생성하여 각 인덱스의 마지막 위치를 저장하였다.

새로운 위치인 newPos에는 1을 더해 트리를 업데이트 해주고, 원래의 위치인 oldPos에는 -1을 더해 트리를 업데이트 해주었다.

펜윅트리의 sum(num) 함수는 num 인덱스 까지의 합을 구해주는 함수이다.
자기 자신까지 카운팅이 되므로, 정답을 출력할때는 1을 빼주어야 한다.

---

3. 소스코드

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

int tc, n, m, tree[4 * 100001];

int sum(int pos) {
    int ret = 0;
    while(pos) {
        ret += tree[pos];
        pos &= (pos - 1);
    }

    return ret;
}

void update(int pos, int val) {
    while(pos <= n + m) {
        tree[pos] += val;
        pos += (pos & -pos);
    }
}

int main() {
    for(scanf("%d", &tc); tc--;) {
        int pos[100001];
        memset(pos, 0, sizeof(pos));
        memset(tree, 0, sizeof(tree));
        scanf("%d %d", &n, &m);

        for(int i = 0; i < n; i++) {
            update(i + m + 1, 1);
            pos[i + 1] = i + m + 1;
        }

        for(int s, i = 0; i < m; i++) {
            scanf("%d", &s);
            printf("%d ", sum(pos[s]) - 1);

            int newPos = m - i;
            int oldPos = pos[s];
            pos[s] = newPos;

            update(newPos, 1);
            update(oldPos, -1);
        }

        printf("\n");
    }
}