https://www.acmicpc.net/problem/3653 3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net # Approach) 선형배열의 업데이트와 쿼리문이니 세그먼트 트리를 떠올리자.
해당 포스트에서는 비재귀 세그먼트 트리를 이용하였다. # Point) DVD의 번호를 기준으로 세그먼트 트리를 만들면 로직이 꼬이기때문에 DVD 컬렉션상의 특정 위치의 DVD의 존재 유무를 기준으로 잡는 것이 좋다. DVD 하나를 빼서 맨 위로 올리는 것을 ‘액션’이라고 하자. 트리의 원본배열의 크기(구간합이 아닌 리프노드의 값들의 배열을 원본 배열이라고 하자)를 n으로 잡는다면 이 액션을 처리하기가 매우 까다롭기에 n+m+1으로 잡는다. 이 배열을 $arr$이라 하고 순서대로 $arr[m+1]$이 최상단 ~ $arr[m+n]$을 최하단으로 두면 초기상태의 $arr$은
$arr[m+1] = 1$(최상단에 dvd가 존재), … , $arr[m+n] = 1$로 모든 $m+1~m+n$에 대해서 1의 값을 가지게 될것이다. 액션이 발생하면 DVD들 간의 순서에 변화가 생기기때문에 DVD의 배열 arr상의 인덱스를 midx라는 배열로 저장해둘것이다.
한번에 액션에 대해 arr과 midx를 업데이트해준후 이에 따라 트리도 갱신해주면 문제가 해결된다. 예를 들어 보자.
$n = 3, m = 1$)
컬렉션은 (최상단 1 2 3 최하단) 이와 같은 형태를 하고 있을 것이다.
초기상태 => $arr[m+1] ~ arr[m+3] = 1$, $midx[1] = m+1$, $midx[2] = m + 2$, $midx[3] = m + 3$
2번영화의 DVD를 빼는 1번의 액션을 취해보자.
1
arr[midx[2]] = 0, arr[insertIdx] = 1, midx[2] = insertidx--;
$arr$상의 2번영화가 존재하는 인덱스(즉, $arr[midx[2]]$)의 값을 0으로, 적절한 위치의 인덱스 $insertIdx$를 잡아서 $arr[insertIdx]$의 값을 1로 갱신해줌으로써 $arr$의 갱신이 완료된다.
이때 $arr$상에선 인덱스가 작을수록 위에 있는 것이므로 $insertIdx$를 계속 감소시키면서 갱신해주면
항상 최상단에 뺀 DVD를 다시 놓는것이 된다.
초기값으로는 초기상태의 1번DVD보다 위인 $insertIdx = m$으로 둔다. $midx[2] = insertIdx$로 갱신해줌으로써 $midx$의 갱신도 완료되어 한번의 액션에 대한 처리가 완료된다. 하단의 코드는 비재귀 세그먼트 트리를 이용하였다. #Code(c++)
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cstring>
#include <stack>
#include <cmath>
#include <tuple>
#include <deque>
#include <climits>
#include <float.h>
// #include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define command_param int argc, char *argv[]
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i < n; i++)
#define FOR(i, s, e) for(int i = s; i < e; i++)
#define pf first
#define ps second
#define pii pair<int,int>
#define ll long long
#define lll __int128
#define endl "\n"
#define nulls '\0'
#define dkdk " "
const int INF = 987654321;
const int mod = (int)1e9+7;
const ll INFLL = 1e13;
const int N = (int)1e5 + 1;
int n, t, sn, m;
int seg[4*N];
int midx[N];
int insertIdx;
void init() {
memset(seg, 0, sizeof(seg));
memset(midx, 0, sizeof(midx));
sn = n + m + 1;
for1(i, n+1) {
midx[i] = i + sn + m; // sn(=0) sn + 1 ~ sn + m// sn + m + 1 ~ sn + m + n
seg[i+sn+m] = 1;
}
for(int i = sn - 1; i; i--) seg[i] = seg[i<<1] + seg[i<<1|1];
insertIdx = sn + m;
}
void action(int idx) {
//get
int sum = 0;
for(int l = sn, r = midx[idx]; l < r; l>>=1, r>>=1) {
if(l & 1) sum += seg[l++];
if(r & 1) sum += seg[--r];
}
cout << sum << dkdk;
//update
seg[midx[idx]] = 0;
for(int i = midx[idx]; i > 1; i>>=1) seg[i>>1] = seg[i] + seg[i^1];
midx[idx] = insertIdx--;
seg[midx[idx]] = 1;
for(int i = midx[idx]; i > 1; i>>=1) seg[i>>1] = seg[i] + seg[i^1];
}
int main() {
FASTIO;
cin >> t;
while(t--) {
cin >> n >> m;
init();
for0(i, m) {
int in; cin >> in;
action(in);
}
cout << endl;
}
return 0;
}