:platinum5: 3516. John’s Inversions

r 순으로 정렬하고 b에서의 inversion count를 세면 됩니다.

증명) 임의의 두 카드 쌍을 골라 $(r_1, b_1)$, $(r_2, b_2)$라고 합시다. 또, WLOG $r_1\leq r_2$라 합시다.

• $b_1\leq b_2$인 경우, 쌍 1을 무조건 앞에 놓아야 합니다.
• $b_1 > b_2$인 경우, 어떻게 배치하든 inversion 쌍은 하나만 생깁니다.

■