【題解】TIOJ 1080 . A.逆序數對

【題目敘述】https://tioj.ck.tp.edu.tw/problems/1080

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int Case, n, a[100005], bit[100005];
long long ans;
vector <int> v;

int get_id(int x){
    return lower_bound(v.begin(), v.end(), x)-v.begin()+1;
}
void update(int x){
    while (x <= n){
        bit[x]++;
        x += x & (-x);
    }
}
int query(int x){
    int ret = 0;
    while (x){
        ret += bit[x];
        x -= x & (-x);
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    while (cin >> n){
        if (n == 0) break;
        v.clear();
        ans = 0;
        for (int i = 0; i < n; i++){
            cin >> a[i];
            bit[i] = 0;
            v.push_back(a[i]);
        }
        bit[n] = 0;
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        for (int i = 0; i < n; i++){
            ans += i-query(get_id(a[i]));
            update(get_id(a[i]));
        }
        Case++;
        cout << "Case #" << Case << ": " << ans << "\n";
    }
}
分享本文 Share with friends