2024 全國模擬賽題目上線啦 !!!!! 題目在這裡～
1080 . A.逆序數對
TopCoder
Description
對一個數列 $S$ 來說，若 $S$ 的第 $i$ 項 $s_i$ 與第 $j$ 項 $s_j$ 符合 $s_i > s_j$，並且 $i < j$ 的話，那麼我們說 $(i, j)$ 是一個逆序數對。請問給定 $S$，總共有多少個逆序數對呢？
Input Format
輸入檔可能包含多筆測試資料，每筆測試資料第一列會有一個正整數 $n$ （$1 \leq n \leq 10 ^ 5$），第二列有 $n$ 個整數依序為數列 $S$ 的每一項，以一個空白隔開。當 $n=0$ 的時候代表輸入結束，你不必對這筆資料作處理。所有數字都可以用有號32-bit整數型態儲存。
Output Format
對於每組測試資料請先輸出這是第幾個序列，然後是該序列的逆序數對的總數。請參考Sample Output。
Sample Input 1
5
1 2 3 4 5
5
1 2 3 5 4
0
1 2 3 4 5
5
1 2 3 5 4
0
Sample Output 1
Case #1: 0
Case #2: 1
Case #2: 1
Hints
註：請盡量不要使用cin處理輸入，否則極有可能會TLE。
Problem Source
原TIOJ1080 / 經典問題練習。Problem Setter: Tmt。
2021.03.01 Update: Added $\LaTeX$ by FHVirus
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 100 |