Những Cặp Đảo Thứ Tự · canuc80k1603

Cho dãy số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Một cặp chỉ số $(u, v)$ được gọi là nghịch thế khi đồng thời thỏa mãn:

$1 \leq u < v \leq n$ ;
$a_{u} > a_{v}$ .

Hãy đếm tổng số nghịch thế của dãy. Hai phần tử bằng nhau không tạo thành nghịch thế.

Input

Dòng đầu chứa số nguyên $n$ .
$n$ số nguyên tiếp theo lần lượt là $a_{1}, a_{2}, \dots, a_{n}$ . Các số này có thể nằm trên một hoặc nhiều dòng.

Output

In một số nguyên duy nhất: số nghịch thế của dãy.

Constraints

$1 \leq n \leq 6 \cdot 1 0^{4}$ .
$1 \leq a_{i} \leq 6 \cdot 1 0^{4}$ .
Kết quả nằm trong miền của số nguyên có dấu $64$ -bit.

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 3000$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Bốn nghịch thế bắt đầu tại giá trị $4$ ; hai nghịch thế bắt đầu tại giá trị $3$ ; và giá trị $5$ tạo thêm một nghịch thế với số $2$ cuối cùng. Tổng cộng có $7$ cặp.

Phân tích: Khi quét dãy từ trái sang phải, tại vị trí i ta chỉ cần biết có bao nhiêu phần tử trước đó lớn hơn a[i]. Nếu đã xử lý i-1 phần tử và biết số phần tử không lớn hơn a[i], số phần tử lớn hơn là
Phân tích: (i-1) - count(giá trị ≤ a[i]).
Phân tích: Fenwick Tree có thể lưu tần suất theo giá trị. Nén tọa độ giúp lời giải vẫn áp dụng được ngay cả khi miền giá trị không liên tục.
Thuật toán: Sắp xếp và loại trùng các giá trị để gán hạng tăng dần cho từng a[i].
Thuật toán: Khởi tạo Fenwick tần suất bằng 0.
Thuật toán: Duyệt i từ 1 đến n:
Thuật toán: gọi rank là hạng của a[i];
Thuật toán: cộng vào đáp án (i-1) - prefix(rank);
Thuật toán: tăng tần suất tại rank thêm 1.
Thuật toán: Dùng số nguyên 64-bit cho đáp án.
Chứng minh: Trước khi xử lý vị trí i, Fenwick chứa đúng tần suất của các phần tử a[1..i-1]. Vì thứ tự hạng bảo toàn quan hệ so sánh, prefix(rank(a[i])) đếm chính xác các phần tử trước đó có giá trị ≤ a[i].
Chứng minh: Do đó (i-1)-prefix(rank(a[i])) đếm đúng các chỉ số u<i với a[u]>a[i], tức mọi nghịch thế có đầu phải bằng i. Mỗi nghịch thế có đúng một đầu phải nên được cộng đúng một lần, và cặp bằng nhau không bị tính. Tổng cuối cùng là số nghịch thế cần tìm.
Độ phức tạp: Nén tọa độ và quét Fenwick mất O(n log n) thời gian; bộ nhớ là O(n).