Hoán vị nghịch thế

Tác giả:

Dạng bài

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Cho hoán vị \(A = (a_1 , a_2 ,..., a_N)\) của \(N\) số nguyên dương đầu tiên \(1, 2,..., N (2 ≤ N ≤ 1000)\). Một thuận thế của \(A\) là dãy \(B = (b_1 , b_2 ,..., b_N)\) trong đó \(b_i\) là số lượng các phần tử nhỏ hơn \(a_i\) và đứng trước \(a_i\).

Yêu cầu: Cho một hoán vị \(A\), tính thuận thế \(B\) của \(A\).

Input

Dòng đầu ghi số \(N\).
Dòng thứ hai chứa hoán vị \(A\).

Output

Ghi ra thuận thế \(B\) của hoán vị \(A\).

Example

Test 1

Input

9
2 1 7 6 5 4 3 8 9

Output

0 0 2 2 2 2 2 7 8

Bình luận

`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

1 bình luận nữa