Editorial for Hoán vị nghịch thế

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Spoiler Alert

Hint 1

  • Duyệt trâu từng phần tử \(a_i\)

Đếm số lượng phần tử \(a_j\) thỏa \(j < i\) và \(a_j < a_i\)

Reference AC code | \(O(n ^ 2)\) time | \(O(1)\) auxiliary space | Brute-forces

C++
int main()
{
    /// Nhan mang
    int n = readInt();
    vector<int> a(n);
    for (int &x : a)
        cin >> x;

    /// Duyet tung phan tu a[i]
    for (int i = 0; i < n; ++i) {
        int dem = 0;
        for (int j = 0; j < i; ++j) /// Dem so luong phan tu a[j] thoa (j < i) va (a[j] < a[i])
            dem += a[j] < a[i];

        /// Xuat ket qua
        cout << dem << ' ';
    }
    return 0;
}

Question

  • Bạn có thể giải bài trên trong \(O(n\) \(log_2 n)\) ?

Hint: Segment Tree, Order Statistic Tree


Comments

There are no comments at the moment.