MAGB - Đếm số nghịch thế

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Tác giả:
Hiếu Nguyễn
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Cho một dãy gồm ~n~ số nguyên ~a_1, a_2, …, a_n~, đếm số cặp số mà số đứng sau nhỏ hơn số đứng trước. Tức là đếm số cặp ~a_i, a_j~ mà ~i < j~ và ~a_i > a_j~.

Input

  • Dòng đầu tiên chứa duy nhất một số nguyên dương ~n~ (số phần tử trong dãy);
  • Dòng thứ hai chứa ~n~ số nguyên là các phần tử ~a_1, a_2, …, a_n~

Giới hạn:

  • ~1≤n≤10^5,1≤a_i≤10^5~

Output

  • In ra trên một dòng số nguyên duy nhất là số cặp nghịch thế của dãy.

Sample

Input #1
5
2 1 1 2 3
Output #1
2
Input #2
5
3 1 3 1 2
Output #2
5

Problem source: Chuyên Sơn La Online Judge

Bình luận

Please read the guidelines before commenting.


  • 0
    congtyluuthaibao1978  đã bình luận lúc 27, Tháng 11, 2025, 12:25

    include <bits/stdc++.h>

    using namespace std; using ll = long long;

    // Fenwick tree / BIT hỗ trợ update và query prefix sum struct Fenwick { int n; vector<ll> f; Fenwick(int n): n(n), f(n+1, 0) {} // add value v at position i (1-based) void update(int i, ll v) { for (; i <= n; i += i & -i) { f[i] += v; } } // query sum from 1..i (inclusive) ll query(int i) { ll s = 0; for (; i > 0; i -= i & -i) { s += f[i]; } return s; } };

    int main(){ ios::syncwithstdio(false); cin.tie(nullptr);

    int n;
cin >> n;
vector<int> a(n);
int maxA = 0;
for(int i = 0; i < n; i++){
    cin >> a[i];
    if(a[i] > maxA) maxA = a[i];
}

Fenwick bit(maxA + 5);
ll inv = 0;

// Duyệt từ trái → phải. Với mỗi a[i], số j < i với a[j] > a[i] = 
// tổng các phần tử đã xuất hiện – số phần tử ≤ a[i]
for(int i = 0; i < n; i++){
    // tổng phần tử đã xuất hiện: i
    // số phần tử ≤ a[i]: bit.query(a[i])
    ll greater_before = i - bit.query(a[i]);
    inv += greater_before;

    // đánh dấu hiện tại
    bit.update(a[i], 1);
}

cout << inv << "\n";
return 0;

    }