Codeforces Round 790 (Div. 4)

Dashboard - Codeforces Round 790 (Div. 4) - Codeforces

 

H2

i < j 이고 ai >= aj 인 순서쌍 (i, j)의 개수를 세면 됨

 

방법 1 - BIT(fenwick tree)

배열의 왼쪽부터 오른쪽으로 차례로 보자. 지금까지 본 원소(왼쪽에 있는 원소)들 중 본인보다 작거나 같은 수의 개수를 세면 된다.

이를 위해 누적합의 다음 성질을 이용한다. 편의상 index 0은 생각하지 않기로 한다.
0으로 초기화된 배열 A에 대해, B를 배열 A의 누적합이라고 하자. i.e. B[i] = A[1] + A[2] + ... + A[i]
A[1] 에 1을 더하면 B의 모든 원소는 1 증가한다.
한편 A[n] 에 1을 빼면 B[n]을 포함하여 B[n] 오른쪽의 원소들은 모두 1 감소한다.

이로써 A[1] += 1; A[n+1] -= 1 두 연산만으로 B[1...n] += 1 의 효과를 얻을 수 있다.
이제 B[num] := (num 보다 크거나 같은 수의 개수) 라고 정의하고 문제를 풀면 된다.

 

방법 2 - Segment tree

방법 1과 동일한 논리를 segment tree/lazy propagation으로 구현한 것이다.

 

방법 3 - Inversion count in Array using Merge Sort

Inversion count in Array using Merge Sort - GeeksforGeeks