MathTrauma

문제 링크 : https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 입력된 순서 index 와 값을 정렬했을 때 순서가 엇갈린 개수를 찾는 문제이다. 문제의 기술에서는 인접한 두 수만을 비교하지만 멀리 떨어져 있어도 언젠가는 비교해서 swap 된다. 우선 문제의 카테고리는 세그먼트 트리이지만 다른 풀이부터 보자. 1. Merge Sort 가장 직관적인 해법은 실제 버블 소트를 구현해서 swap 개수를 구하는 것이다. 그러나 $..

일차원부터 짧게 언급해 둔다. 원래 수열을 arr 이라 하자. 통상적인 구현에서 segment tree 1 번은 arr 전체를 관리하고, 2 번은 좌측 절반, 3 번은 우측 절반, ... 이런 식으로 segment tree 의 각 원소는 원래 수열의 일정 범위를 관리하는 node 라는 사실은 2 차원이던 3차원이던 변함없다. 즉, tree[2][3] 은 앞의 절반의 행에 관한 정보와 뒤의 절반에 해당되는 원래 수열의 원소들에 관한 정보를 가진다. tree[2][4] 는? 행에 관해서는 앞의 절반 그리고 열에 대해서는 첫 4분 구간에 대한 정보를 가질 것이다. 뭐 code 는 복잡해졌지만 위의 내용만 염두에 두면 번거롭기는 하지만 논리적으로 어렵지는 않다. 아래 구현에서는 i, y 가 행을 나타내고, j,..

문제 링크 : https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 입력값을 차례대로 입력받는다 가정. 이전 입력 값들 중 현재 입력받는 값보다 작은 값들의 누적 개수를 기록할 자료 구조가 필요. 펜윅 트리(Fenwick Tree) 를 사용하기로 한다. 펜위 트리 구조의 요약. index 가 1부터 출발하는 Fenwick Tree 의 경우 약수인 최대의 $2^n$ 개만큼 앞의 원소들의 합을 보관한다. 1 로 끝나면 약수인 2의 거듭제곱 중 ..