Trong khoa học máy tính, một cặp nghịch thế (inversion) trong một mảng hoặc danh sách là một cặp chỉ số (i, j) sao cho i < j nhưng phần tử tại vị trí i lại lớn hơn phần tử tại vị trí j (tức là arr[i] > arr[j]). Việc đếm tổng số cặp nghịch thế là một bài toán kinh điển với nhiều ứng dụng trong phân tích dữ liệu và đánh giá mức độ "sắp xếp" của một mảng.

Có nhiều thuật toán để giải quyết bài toán này, trong đó các phương pháp dựa trên Cây Fenwick (Fenwick Tree hay Binary Indexed Tree - BIT), thuật toán sắp xếp trộn (Merge Sort) và Cây phân đoạn (Segment Tree) là phổ biến và hiệu quả nhất, đều đạt độ phức tạp thời gian O(N log N).

1. Đếm cặp nghịch thế bằng Cây Fenwick (BIT)

Cây Fenwick (BIT) là một cấu trúc dữ liệu cho phép tính tổng tiền tố và cập nhật phần tử trong một mảng một cách hiệu quả. Để đếm số cặp nghịch thế sử dụng BIT, chúng ta có thể áp dụng một kỹ thuật dựa trên việc xử lý các phần tử theo thứ tự giá trị giảm dần. Các giá trị trong mảng đầu vào có thể rất lớn, và kỹ thuật này xử lý vấn đề đó bằng cách sử dụng các chỉ số gốc làm khóa trong BIT.

Quy trình thực hiện như sau:

1. Tạo một mảng các cặp (giá trị, chỉ số gốc) cho tất cả các phần tử trong mảng ban đầu. Chỉ số gốc thường là 1-based (từ 1 đến N).
2. Sắp xếp mảng các cặp này theo giá trị giảm dần. Nếu hai giá trị bằng nhau, chúng ta sắp xếp theo chỉ số gốc giảm dần. Điều này đảm bảo rằng các phần tử có giá trị lớn hơn hoặc các phần tử có cùng giá trị nhưng chỉ số gốc lớn hơn sẽ được xử lý trước.
3. Duyệt qua mảng các cặp đã sắp xếp:
   • Với mỗi cặp (giaTriHienTai, chiSoGoc), cập nhật cây Fenwick tại vị trí chiSoGoc bằng cách thêm 1. Điều này đánh dấu rằng phần tử tại chiSoGoc đã được "nhìn thấy".
   • Tổng số cặp nghịch thế tăng thêm giá trị của tổng tiền tố trong BIT từ 1 đến chiSoGoc - 1. Bởi vì chúng ta đang xử lý các giá trị lớn hơn trước, bất kỳ phần tử nào đã được đánh dấu trong BIT (nghĩa là có chỉ số gốc nhỏ hơn chiSoGoc và đã được xử lý) sẽ tạo thành một cặp nghịch thế với phần tử hiện tại. (Phần tử j với j < chiSoGoc và arr[j] > arr[chiSoGoc]). Việc sắp xếp thứ cấp theo chiSoGoc giảm dần cho các giá trị bằng nhau đảm bảo rằng các trường hợp arr[j] == arr[chiSoGoc] không bị tính.

Ví dụ minh họa (dựa trên bài toán Luogu P1908):

#include <iostream>
#include <vector>
#include <algorithm> // Để sử dụng std::sort

// Kích thước tối đa của mảng, có thể cần điều chỉnh
const int MAX_SIZE = 500005;

// Mảng cây Fenwick (sử dụng 1-based indexing)
long long cayFenwick[MAX_SIZE];
int kichThuocMang; // Kích thước thực tế của mảng đầu vào

// Hàm cập nhật giá trị tại chỉ số 'idx' trong cây Fenwick
// 'val' là giá trị muốn thêm vào (thường là 1)
void capNhat(int idx, int val) {
    for (; idx <= kichThuocMang; idx += (idx & -idx)) {
        cayFenwick[idx] += val;
    }
}

// Hàm lấy tổng tiền tố từ 1 đến 'idx' trong cây Fenwick
long long layTong(int idx) {
    long long tong = 0;
    for (; idx > 0; idx -= (idx & -idx)) {
        tong += cayFenwick[idx];
    }
    return tong;
}

// Cấu trúc để lưu trữ giá trị và chỉ số gốc
struct PhanTuGoc {
    int giaTri;
    int chiSoGoc; // Chỉ số của phần tử trong mảng ban đầu (1-based)
};

// Hàm so sánh tùy chỉnh cho việc sắp xếp mảng PhanTuGoc:
// 1. Sắp xếp theo giaTri giảm dần.
// 2. Nếu giaTri bằng nhau, sắp xếp theo chiSoGoc giảm dần.
bool soSanhPhanTu(const PhanTuGoc& a, const PhanTuGoc& b) {
    if (a.giaTri != b.giaTri) {
        return a.giaTri > b.giaTri; // Sắp xếp giảm dần theo giá trị
    }
    return a.chiSoGoc > b.chiSoGoc; // Nếu giá trị bằng nhau, sắp xếp giảm dần theo chỉ số gốc
}

int main() {
    // Tối ưu hóa I/O
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> kichThuocMang;

    std::vector<PhanTuGoc> mangPhanTu(kichThuocMang);
    for (int i = 0; i < kichThuocMang; ++i) {
        std::cin >> mangPhanTu[i].giaTri;
        mangPhanTu[i].chiSoGoc = i + 1; // Lưu chỉ số gốc (1-based)
    }

    // Sắp xếp mảng theo tiêu chí đã định
    std::sort(mangPhanTu.begin(), mangPhanTu.end(), soSanhPhanTu);

    long long demNghichThe = 0;

    // Duyệt qua các phần tử đã sắp xếp
    for (int i = 0; i < kichThuocMang; ++i) {
        // Cập nhật cây Fenwick tại chỉ số gốc của phần tử hiện tại
        // Đánh dấu rằng phần tử tại chiSoGoc này đã được xử lý
        capNhat(mangPhanTu[i].chiSoGoc, 1);
        
        // Đếm số phần tử có chỉ số gốc nhỏ hơn (đứng trước trong mảng ban đầu)
        // và đã được xử lý (tức là có giá trị lớn hơn hoặc bằng phần tử hiện tại)
        // Đây chính là số cặp nghịch thế mà phần tử hiện tại tạo ra với các phần tử đứng trước nó
        demNghichThe += layTong(mangPhanTu[i].chiSoGoc - 1);
    }

    std::cout >> demNghichThe << std::endl;

    return 0;
}

2. Đếm cặp nghịch thế bằng Sắp xếp trộn (Merge Sort)

Thuật toán sắp xếp trộn (Merge Sort) không chỉ nổi tiếng với việc sắp xếp hiệu quả mà còn có thể dễ dàng được điều chỉnh để đếm số cặp nghịch thế. Ý tưởng chính là tận dụng quá trình "trộn" (merge) hai nửa mảng con đã được sắp xếp.

Khi thực hiện hợp nhất hai nửa mảng con (ví dụ, nửa trái từ batDau đến giua và nửa phải từ giua+1 đến ketThuc), nếu một phần tử từ nửa mảng phải (ví dụ mangGoc[j]) nhỏ hơn một phần tử từ nửa mảng trái (ví dụ mangGoc[i]):

Điều này có nghĩa là mangGoc[j] tạo thành một cặp nghịch thế với mangGoc[i]. Hơn nữa, vì cả hai nửa mảng con đã được sắp xếp, mangGoc[j] cũng sẽ nhỏ hơn tất cả các phần tử còn lại trong nửa mảng trái (từ mangGoc[i] đến mangGoc[giua]). Do đó, số cặp nghịch thế tăng thêm (giua - i + 1).

#include <iostream>
#include <vector> // Có thể bỏ nếu không dùng std::vector, giữ cho chuẩn C++

const int MAX_N_MERGE = 500010;
int mangGoc[MAX_N_MERGE]; // Mảng chứa dữ liệu gốc
int mangTam[MAX_N_MERGE]; // Mảng tạm thời dùng trong quá trình trộn
long long soCapNghichThe = 0; // Biến lưu tổng số cặp nghịch thế

// Hàm sắp xếp trộn và đếm cặp nghịch thế
// 'batDau' và 'ketThuc' là các chỉ số (1-based) của đoạn mảng cần xử lý
void sapXepTronVaDem(int batDau, int ketThuc) {
    if (batDau == ketThuc) {
        return; // Đoạn mảng chỉ có một phần tử, không có cặp nghịch thế nào
    }

    int giua = (batDau + ketThuc) / 2;
    sapXepTronVaDem(batDau, giua);       // Đệ quy sắp xếp và đếm nửa trái
    sapXepTronVaDem(giua + 1, ketThuc); // Đệ quy sắp xếp và đếm nửa phải

    // Bắt đầu quá trình trộn hai nửa đã được sắp xếp
    int i = batDau;     // Con trỏ cho nửa trái
    int j = giua + 1;   // Con trỏ cho nửa phải
    int k = batDau;     // Con trỏ cho mảng tạm mangTam

    while (i <= giua && j <= ketThuc) {
        if (mangGoc[i] <= mangGoc[j]) {
            // Phần tử từ nửa trái nhỏ hơn hoặc bằng phần tử từ nửa phải.
            // Không tạo nghịch thế với phần tử hiện tại của nửa phải.
            // Đưa phần tử từ nửa trái vào mảng tạm.
            mangTam[k++] = mangGoc[i++];
        } else {
            // Phần tử từ nửa phải (mangGoc[j]) nhỏ hơn phần tử từ nửa trái (mangGoc[i]).
            // Đây là một cặp nghịch thế.
            // Hơn nữa, mangGoc[j] sẽ nhỏ hơn mangGoc[i] VÀ tất cả các phần tử còn lại
            // trong nửa trái (từ chỉ số i đến chỉ số giua).
            soCapNghichThe += (long long)(giua - i + 1);
            // Đưa phần tử từ nửa phải vào mảng tạm.
            mangTam[k++] = mangGoc[j++];
        }
    }

    // Sao chép các phần tử còn lại từ nửa trái (nếu có)
    while (i <= giua) {
        mangTam[k++] = mangGoc[i++];
    }

    // Sao chép các phần tử còn lại từ nửa phải (nếu có)
    while (j <= ketThuc) {
        mangTam[k++] = mangGoc[j++];
    }

    // Sao chép các phần tử đã trộn từ mangTam về lại mangGoc
    for (int l = batDau; l <= ketThuc; ++l) {
        mangGoc[l] = mangTam[l];
    }
}

int main() {
    // Tối ưu hóa I/O
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n; 
    for (int i = 1; i <= n; ++i) { // Sử dụng 1-based indexing cho mảng
        std::cin >> mangGoc[i];
    }

    sapXepTronVaDem(1, n); // Bắt đầu sắp xếp và đếm từ chỉ số 1 đến n

    std::cout >> soCapNghichThe << std::endl;

    return 0;
}

3. Đếm cặp nghịch thế bằng Cây phân đoạn (Segment Tree)

Cây phân đoạn (Segment Tree) cũng có thể được sử dụng để đếm cặp nghịch thế, với nguyên lý hoạt động tương tự như cây Fenwick nhưng có thể linh hoạt hơn trong một số trường hợp (ví dụ, khi cần các truy vấn phức tạp hơn). Để áp dụng Segment Tree:

1. **Nén tọa độ:** Nếu các giá trị trong mảng lớn (ví dụ, vượt quá giới hạn có thể dùng làm chỉ số cây), trước tiên cần nén tọa độ chúng về một phạm vi nhỏ hơn (ví dụ từ 1 đến N hoặc số lượng phần tử phân biệt).
2. **Xây dựng Segment Tree:** Xây dựng một Segment Tree trên phạm vi các giá trị đã nén (hoặc các giá trị nếu chúng đã đủ nhỏ). Mỗi nút trong cây sẽ lưu trữ số lần xuất hiện (tần suất) của các giá trị trong đoạn mà nút đó đại diện.
3. **Duyệt mảng gốc:** Duyệt qua từng phần tử arr[i] của mảng gốc theo thứ tự ban đầu:
   • **Truy vấn:** Để đếm số cặp nghịch thế mà arr[i] tạo ra với các phần tử đứng trước nó, bạn cần tìm số lượng phần tử đã được thêm vào cây (đã xử lý trước đó) mà có giá trị lớn hơn arr[i]. Bạn thực hiện điều này bằng cách truy vấn tổng tần suất trong Segment Tree cho đoạn từ rank(arr[i]) + 1 đến max_rank (trong đó rank(arr[i]) là giá trị đã nén của arr[i]).
   • **Cập nhật:** Tăng tần suất của arr[i] trong Segment Tree (thực hiện cập nhật điểm) để đánh dấu rằng arr[i] đã được xử lý và có mặt trong tập dữ liệu.

Tổng các giá trị truy vấn được trong bước 3 sẽ là tổng số cặp nghịch thế của mảng.