Viết chương trình nhập vào n (0<n100 ) số nguyên. In ra số lượng các cặp a[i] và a[j] thỏa mãn i < j và a[i] > a[j] trong dãy số. Dữ liệu vào Dòng đầu tiên ghi số nguyên không âm n. Dòng 2 ghi n số nguyên dương 64bit cách nhau một dấu cách trống. Kết quả Đưa ra số lượng các cặp a[i] và a[j] thỏa mãn i < j và a[i] > a[j]. INPUT 5 1 3 2 4 5 OUTPUT 1

#include <bits/stdc++.h>
#define ll long long int
#define endl '\n'

using namespace std;

const ll N = 1e5 ;
ll n, a, st[4*N+5]={}, ans=0 ;

void build(ll id, ll l, ll r, ll a) {
    if ( (l > a) || (r < a) || (l > r)) return ;
    if (l == r) {
        st[id]++ ;
        return ;
    }
    ll md = (l + r) / 2 ;
    build(id*2, l, md, a) ;
    build(id*2+1, md+1, r, a) ;
    st[id] = st[id*2] + st[id*2+1] ;
}

ll find_sum(ll id, ll l, ll r, ll x, ll y) {
    if ( (l > y) || (r < x) || (l > r)) return 0 ;
    if ( (l >= x) && (r <= y)) return st[id] ;
    ll md = (l + r) / 2;
    return find_sum(id*2, l, md, x, y) + find_sum(id*2+1, md+1, r, x, y) ;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n ;
    for ( ll i=1 ; i <= n ; i++) {
        cin >> a ;
        ans += find_sum(1, 1, N, a+1, N) ;
        build(1,1, N, a) ;
    }

    cout << ans ;

}