Hướng dẫn cho Hoán vị nghịch thế

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame

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


Bình luận

Không có bình luận nào.