[백준]3653_영화 수집(C++)

세그먼트 트리를 사용해서 해결 했습니다.

트리의 리프노드의 갯수를 n + m 개로 셋팅한뒤에

현재 k번째 리프노드가 제일위의 책의 위치라면

다음 위로올라가는 책은 k + 1 번째의 리프노드에 업데이트 해주었습니다.

최대 tree의 배열크기를 (10만 + 10만) * 4 + 1 로 해주어야 20만개의 리프노드를 처리가능합니다.

---

tree의 0번째 노드 : 제일밑에있는 책의 인덱스

tree의 n-1번째 노드 : 제일 위에있는 책의 인덱스

query로 자신보다 오른쪽에 있는 값을 리턴하고

자기 자신이 있던 노드를 0으로 업데이트해준뒤

유효한 리프노드 + 1 번째( 올라가게되는 위치 ) 를 1로 업데이트 해줍니다.

 

#include <iostream>
using namespace std;

#define MAX_N 100001
#define MAX_M 100001
int tree[MAX_N * 8]; 
int ans[MAX_M], arr[MAX_N];

int update_tree(int now, int target, int start, int end, int value) {
     if (target > end || target < start) return tree[now];
     if (start == end) {
          tree[now] = value;
          return tree[now];
     }
     int mid = (start + end) / 2;
     tree[now] = update_tree(now * 2, target, start, mid, value) + update_tree(now*2+1,target,mid+1,end, value);
     return tree[now];
}

int query(int now, int left, int right, int start, int end) {
     if (left > end || right < start) return 0;
     if (left <= start && end <= right)  return tree[now];
     int mid = (start + end) / 2;
     return query(now * 2, left, right, start, mid) + query(now * 2 + 1, left, right, mid + 1, end);
}

int main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int T; cin >> T;
     while (T--) {
          int n, m;
          cin >> n >> m;
          int size = n + m - 1;
          for (int i = 0; i < n+m; i++) {
               if (i < n)
                    update_tree(1, i, 0, size, 1);
               else
                    update_tree(1, i, 0, size, 0);
               
          }
          for (int i = n; i >= 1; i--) {
               arr[i] = (n - i);
          }
       
          for (int i = 0; i < m; i++) {
               int data; cin >> data;
               int target = arr[data];
               ans[i] = query(1, target+1, size, 0, size);
               update_tree(1, target, 0, size, 0);
               update_tree(1, n, 0, size, 1);
               arr[data] = ++n;
          }
          for (int i = 0; i < m; i++) {
               cout << ans[i] << " ";
          }
          cout << "\n";
     }
}