입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 100개를 넘지 않는다.
각 테스트 케이스의 첫째 줄에는 상근이가 가지고 있는 영화의 수 n과 보려고 하는 영화의 수 m이 주어진다. (1 ≤ n, m ≤ 100,000) 둘째 줄에는 보려고 하는 영화의 번호가 순서대로 주어진다.
영화의 번호는 1부터 n까지 이며, 가장 처음에 영화가 쌓여진 순서는 1부터 증가하는 순서이다. 가장 위에 있는 영화의 번호는 1이다.
출력
각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD를 가장 위에 놓는다.
그냥 배열 스왑으로 하자니 범위가 너무 커서 감이 안 와서 검색해본 결과, 세그먼트 트리로 범위를 두배잡는 형식으로 푸는 방법을 찾았다.
영화 갯수가 N개라면 세그먼트 트리의 리프노드의 갯수를 N*2로 잡고, 영화를 볼때마다 N 다음 인덱스에 차곡차곡 넣는 느낌이다.
N 다음 인덱스에 넣기 위해선 인덱스가 거꾸로 정렬되어있어야한다.
N-1부터 0까지 정렬되어있기 위해서 인덱스 관리용 index배열을 하나 생성해준 후,
for (int j = 0; j < n; j++) {
//책을 쌓을 공간이 인덱스 증가하는 방향으로 생기므로
//인덱스값들을 반대로 쌓아야한다.
index[j] = n-j-1;
N-j-1씩 넣어준다.
그 후, 인덱스 0부터 n-1까지 1을 넣고 구간합 세그먼트 트리를 구성한다.
입력값을 받을때 해당 입력값에 해당하는 인덱스 번호를
index배열에서 조회한 후, [해당 인덱스 +1,끝]구간에 해당하는 구간합을
출력한다.
for (int j = 0; j < m; j++) {
cin >> tmpInput;
//tmpInput위치에 해당하는 인덱스를 index배열에서 조회한 뒤, 해당 인덱스+1 부터 끝까지의 구간합 출력
cout << findHowManyDvdsInTargetRange(index[--tmpInput]+1, firstLeafNodeIdx * 2, 1, 0, firstLeafNodeIdx - 1) << " ";
세그먼트 트리의 해당인덱스에는 -1을 넣고 조상노드들도 -1씩 더하며 갱신해준다.
//해당 노드를 -1로 변경하고 조상노드도 -1씩 빼는식으로 갱신하면서 책을 뺐다는걸 구현
SetAncestorNode(index[tmpInput], -1);
그 후 해당 입력값의 인덱스는 n+j로 변경해준다.
=> 해당 책이맨위에 있다는뜻.
//tmpInput의 인덱스는 이제 맨위인 n+j
index[tmpInput] =n+j;
n+j인덱스인 리프노드를 1더하고 조상노드들도 갱신하며 책을 맨위에 둔걸 구현
//n+j인덱스의 노드를 1을 더하면서 책을 맨위에 둔것으로 구현
SetAncestorNode(index[tmpInput], 1);
#include<iostream>
using namespace std;
//사이즈는 2^19
int segTree[524'288*2];
//인덱스 값 잡아주는 배열
int index[100'000];
int firstLeafNodeIdx = 524288;
int findHowManyDvdsInTargetRange(int targetL, int targetR, int nodeNum, int curL, int curR) {
if (targetR < curL || curR < targetL) return 0;
if (targetL <= curL && curR <= targetR) return segTree[nodeNum];
int mid = (curL + curR) / 2;
return findHowManyDvdsInTargetRange(targetL, targetR, nodeNum * 2, curL, mid) +
findHowManyDvdsInTargetRange(targetL, targetR, nodeNum * 2 + 1, mid + 1, curR);
}
void SetAncestorNode(int idx, int val) {
int tmpIdx = idx + firstLeafNodeIdx;
while (tmpIdx > 0) {
segTree[tmpIdx] += val;
tmpIdx /= 2;
}
}
void Input() {
int testCases=0,n=0,m=0,tmpInput=0;
cin >> testCases;
for (int i = 0; i < testCases; i++) {
fill(segTree, segTree + 524288 * 2, 0);
fill(index, index + 100'000, 0);
cin >> n >> m;
for (int j = 0; j < n; j++) {
//책을 쌓을 공간이 인덱스 증가하는 방향으로 생기므로
//인덱스값들을 반대로 쌓아야한다.
index[j] = n-j-1;
SetAncestorNode(j, 1);
}
for (int j = 0; j < m; j++) {
cin >> tmpInput;
//tmpInput위치에 해당하는 인덱스를 index배열에서 조회한 뒤, 해당 인덱스+1 부터 끝까지의 구간합 출력
cout << findHowManyDvdsInTargetRange(index[--tmpInput]+1, firstLeafNodeIdx * 2, 1, 0, firstLeafNodeIdx - 1) << " ";
//해당 노드를 -1로 변경하고 조상노드도 -1씩 빼는식으로 갱신하면서 책을 뺐다는걸 구현
SetAncestorNode(index[tmpInput], -1);
//tmpInput의 인덱스는 이제 맨위인 n+j
index[tmpInput] =n+j;
//n+j인덱스의 노드를 1을 더하면서 책을 맨위에 둔것으로 구현
SetAncestorNode(index[tmpInput], 1);
}
cout << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
Input();
}
크기를 두 배 늘려서 맨위에 둘때마다 뒤에 두는식으로 갱신하는 방식이
신선했고 재밌었던 문제였다.