Elearning CodePath – CTP Online Judge

Số Nghịch Thế

CINV

🟢 Hard #Sorting #Segment Tree #Fenwick Tree

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho dãy $A$ gồm $N$ số nguyên, $A = (A_1, A_2, \dots, A_N)$.
Một cặp $(i, j)$ được gọi là một **nghịch thế** nếu như: $i < j$ và $A_i > A_j$

Yêu cầu: Đếm xem dãy $A$ có bao nhiêu nghịch thế.

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `CINV.INP`:

* Dòng đầu tiên: Ghi số nguyên dương $N$.
* Dòng thứ hai: Ghi $N$ số nguyên $A_1, A_2, \dots, A_N$ cách nhau bởi dấu cách.

Giới hạn:
* $1 \le N \le 2 \times 10^5$.
* $1 \le A_i \le 10^9$.

---
### 📤 Định dạng Đầu ra

Ghi ra file `CINV.OUT` một số nguyên duy nhất là số lượng nghịch thế tìm được.

---
### ✨ Ví dụ

| Input (`CINV.INP`) | Output (`CINV.OUT`) |
| :--- | :--- |
| `3` <br> `2 1 3` | `1` |

Giải thích:
* Dãy là $(2, 1, 3)$.
* Các cặp $(i, j)$ thỏa mãn $i < j$ và $A_i > A_j$:
    * $(1, 2)$: $i=1, j=2$. $A_1=2, A_2=1$. $2 > 1$. $\rightarrow$ Nghịch thế.
* Tổng số nghịch thế là $1$.

---
### 🏷 Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N \le 5000$ | $40\%$ |
| 2 | $N \le 2 \times 10^5$ | $60\%$ |

---

✅ Đã AC: 2 / 7 submissions