====== Inversion Counting ======
  * 어떤 리스트 A에서, i<j 인데 A[i]>A[j] 인 (i,j)쌍을 inversion이라고 한다. inversion counting은 이런 inversion의 갯수를 세는 것이다.

===== 풀이법 =====
  * 이 문제를 O(nlogn)에 풀 수 있는 방법은, 분할 정복과 Order Statistic Tree를 쓰는 방법의 두가지가 있다.
  * 분할 정복으로 푸는 방법은, 머지 소트를 살짝 변형한 것과 동일하다. 방법은 [[https://www.geeksforgeeks.org/counting-inversions/]]여기 참고.
  * Order Statistic Tree를 쓰는 방법은, 앞에서부터 원소들을 차례대로 set에 추가하면서, set안의 그 원소보다 큰 수의 갯수를 세는 것이다. 이미 set 안에 추가되어있는 원소들은 index가 자신보다 작은 원소들이니까, 이중에서 rank()연산으로 값이 자신보다 큰 원소들의 갯수를 면 된다
  * Python을 기준으로, Order Statistic Tree를 FenwickTree로 구현해서 사용했을 때 보통 범위에서는 실행 속도에 큰 차이가 없었다.
    * 단순한 inversion counting 문제를 봤을때, [[ps:problems:boj:1517]] (n<500,000) 에서는 머지소트쪽이 좀 더 빨랐다. 그러나 좌표압축이 필요 없고, n이 더 커진 [[ps:problems:boj:10090]] (n<1,000,000) 에서는 Order Statistic Tree쪽이 더 빨랐다.
    * 문제에서 할 일이 좀더 많아진 경우, 예를들면 [[ps:problems:boj:2517]] 에서는 Order Statistic Tree쪽이 더 빨랐다.
  * 응용 문제에 적용할 수 있는 확장성면에서도 Order Statistic Tree를 쓰는 것이 더 유리하다.
  * 그래서, inversion counting 관련 문제가 나오면 고민 없이 [[ps:teflib:fenwicktree#OrderStatisticTree|teflib.fenwicktree.OrderStatisticTree]]를 사용해서 풀기로 했다.

===== 확장 =====
 
==== 일반적인 2-tuple에서 풀이 ====
  * 배열에서 i<j 인데 A[i]>A[j] 이 되는 것을 inversion이라고 정의했는데, 이것을 (인덱스, 값)이라는 튜플로 바꿔서 생각하면, P[i] = (i, A[i])인 pair의 리스트로 볼 수 있다. 그러면 이 문제는 P[i].first < P[j].first 이고 P[i].second > P[j].second 인 (i,j)를 찾는 것과 동일하다. 따라서 아무 pair형태의 데이터에서도 이것을 똑같이 적용할 수 있다. 2차원 좌표상의 점들이 대표적인 예다. P_i = (x_i,y_i)라는 점들이 주어질때, x_i < x_j 이면서 y_i > y_j 인 (P_i, P_j)쌍의 갯수를 구하는 것, 다시 말하면 위치 관계가 ↖↘ 방향에 놓여 있는 포인트 쌍의 갯수를 구하는 문제를 똑같은 방식으로 풀 수 있다.
  * 먼저 점들을 x에 대해서 정렬하고, x가 작은 것부터 대응되는 y값을 set에 추가하며, set 안에서 자기보다 더 큰 수의 갯수를 세면 된다.
  *  x_i < x_j이고  y_i < y_j 인 쌍을 구하는 것도 동일하다. 이런 쌍을 보통 dominated pair이라고 부른다 

==== 3-tuple ====
  * 2-tuple에 적용했던 비슷한 아이디어를 3-tuple로 확장시켜보자. 
  * P[i]=(x_i,y_i,z_i)일 때, dominated pair의 갯수를 세는 것은 x_i<x_j, y_i<y_j, z_i<z_j 인 (p[i], p[j])쌍의 갯수를 세는 것이 된다. 이것을 하려면 x에 대해 소팅해서, 어떤 데이터 구조 안에 x값이 더 작은 튜플들만 모아놓는 것까지는 똑같지만, 그 데이터 구조 안에서 y<Y이고 z<Z인 튜플을 찾을 수 있어야 한다. 이것을 지원하려면 Order Statistic Tree를 2차원으로 짜야 한다.
  * 3-tuple에서 좀더 쉬운 문제는 dominated pair의 갯수가 아닌, 존재 여부만 찾는 것이다. 이것은 구간 최솟값 쿼리를 통해서 풀 수 있다. 일단 x에 대해서 정렬해서 x_i<X인 점들만 저장해놓는다. A[y]가 해당되는 점의 z값중 최솟값을 갖도록 저장하면, 이제 y<Y 이고 z<Z인 점이 존재하는 지 여부는 min(A[0:Y]) 가 Z보다 큰지 아닌지를 비교해서 구할 수 있다. 세그먼트 트리를 쓰면 구간 최솟값과 점 추가를 O(logn)에 할 수 있다. 이 문제에서는 쿼리 범위가 항상 0으로 시작하므로 펜윅트리로도 처리할 수 있다. 

==== 세 개의 원소의 inversion ====
  * tuple의 사이즈를 늘리는 대신, 점의 갯수를 늘리는 쪽으로 확장해보자. 즉 x_i < x_j < x_k 이고 y_i < y_j < y_k 인 (i,j,k) 트리플, 또는 3-inversion의 갯수를 찾는 문제로 확장해보자.
  * x에 대해서 정렬해서 순서대로 추가한다는 기본은 변함 없다.
  * (x_k,y_k)를 추가할 때, 이미 저장된 점들로 만들어진 2-inversion (i,j)들 중에서 y_j<y_k 인 것의 갯수를 세어주면 된다.
  * 이를 구현하기 위해서는, y값들을 저장하는 Order Statistic Tree와 2-inversion에서 큰쪽의 y값들을 저장하는 Order Statistic Tree를 따로 만들어서 각각 업데이트해주면 된다.
  * [[ps:problems:boj:5012]]에도 좀더 설명이 있으니 참고.
  * 이걸 더 확장해서 n개의 원소의 inversion을 찾을수도 있다.
    * i번째 원소로 끝나는 (k-1)-inversion의 갯수를 알고 있으면, 거기에서 i번째 원소로 끝나는 k-inversion의 갯수를 OST를 이용해서 구할수가 있다. 이 결과를 다시 저장해두고 여기에서 (k+1)-inversion의 갯수를 구하는 식으로 반복해나간다
    * [[ps:problems:boj:24505]] 참고.


===== 코드 =====
  * [[ps:problems:boj:1517]] 참고.

===== 관련 문제 =====
  * [[ps:problems:boj:1517]] : 가장 기본 문제. 
  * [[ps:problems:boj:2517]] : 조금 응용한 문제
  * [[ps:problems:boj:5419]] : 2-tuple 데이터.
  * [[ps:problems:boj:2336]] : 3-tuple 데이터에서 dominated pair의 존재 여부 찾기
  * [[ps:problems:boj:5012]] : inversion을 이루는 triple 세기