BOJ 3653: 영화 수집

작성일

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

  • 2월동안 187문제 풀기(지난달 누적 87개) (70/187)
  • 아이디어가 필요한 펜윅 트리 문제
  • 아래로 계속 밀어넣어야 한다는 것을 감안하면 위쪽으로 초기값을 밀어놓고 아래쪽에 공간을 확보해야한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;

class FenwickTree {
  int N, h = -1;
  vector<int> tree;

public:
  FenwickTree(int n): N(n), tree(n) {
    while(n) h++, n /= 2;
  }

  void update(int p, int v) {
    while(p < N) {
      tree[p] += v;
      p += (p & -p);
    }
  }

  int query(int p) {
    int res = 0;
    while(p > 0) {
      res += tree[p];
      p -= (p & -p);
    }
    return res;
  }

  int find(int x) {
    int ans = 0;
    for(int e = 1 << h; e > 0; e /= 2) {
      if(tree[ans+e] < x)
        x -= tree[ans+e], ans += e;
    }
    return ans+1;
  }
};

int main() {
  int TC, N, M;
  vector<int> pos;
  scanf("%d", &TC);
  while(TC--) {
    scanf("%d %d", &N, &M);
    FenwickTree ft(M+N+2);
    pos.resize(N+1);
    for(int i = 1; i <= N; i++) {
      ft.update(M+1+i,1);
      pos[i] = M+1+i;
    }

    int top = M+1, movie;
    for(int i = 0; i < M; i++) {
      scanf("%d", &movie);
      ft.update(pos[movie], -1);
      printf("%d ", ft.query(pos[movie]));
      pos[movie] = top--;
      ft.update(pos[movie], 1);
    }
    printf("\n");
  }
}