Dãy nghịch thế

2017-08-01
Bài gốc

SPOJ NKINV

Đề bài

Cho một dãy số a1.. aN. Một nghịch thế là một cặp số u, v sao cho u < v và au > av. Nhiệm vụ của bạn là đếm số nghịch thế.

Giới hạn:

  • 1 ≤ n ≤ 60000
  • 1 ≤ ai ≤ 60000
Định dạng test

Input:

  • Dòng đầu là N.
  • N dòng sau mỗi dòng là một số ai.

Output:

  • Ghi trên một dòng số M duy nhất là số nghịch thế.

Ví dụ:

input:
3
3
1
2
---
2
Thuật toán

Ý tưởng: tại ai, tìm số lượng các aj < ai sao cho j > i.

Từ đây có thể dùng BIT (hoặc IT) để truy vấn cũng như cập nhật số lượng các ai đã duyệt qua.

Source code

Ngôn ngữ: C++.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

const int N = 6e4 + 5;
int n, a[N], BIT[N];

int query(int i) {
    int sum = 0;
    for(; i >= 1; i -= (i&-i))
        sum += BIT[i];
    return sum;
}

void update(int i) {
    for(; i < N; i += (i&-i))
        BIT[i]++;
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    // init
    cin >> n;
    FOR(i,1,n) cin >> a[i];

    // solve
    int res = 0;
    DOW(i,n,1) {
        res += query(a[i] - 1);
        update(a[i]);
    }
    cout << res;

    return 0;
}
Độ phức tạp

O(NlogN)