Uva 11495 Bubbles and Buckets－louisfghbvc的部落格

題目大意: 算逆序數對，判斷數對是奇數還偶數，CPE的話則多印出數值。

思路: 兩種做法，BIT, MergeSort. 這邊用BIT(Binary Index Tree)。很簡短

首先要先知道BIT是甚麼，先假設已經了解BIT。簡單來說用lowbit來加速存取。

至於為啥這裡能用BIT去寫呢。因為題目數值範圍可以用陣列存。如果1e9就只能用別的方法了。

這邊BIT存的是數字，類似數字頻率，所以query(x)的意思就是算在x之前，有多少數字比x小。包含x

那怎麼算比x大的數字有幾個呢(也就是本題要求的)，很簡單用長度減去比x小的。就是我for loop在做的事了。

代碼:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;

int bit[N];

void add(int x, int v){
    for(++x; x < N; x+=x&-x)
        bit[x] += v;
}

int query(int x){
    int res = 0;
    for(++x; x; x-=x&-x)
        res += bit[x];
    return res;
}

int main() {
    //cin.tie(0); ios::sync_with_stdio(false);
    int n;
    while(cin >> n, n){
        memset(bit, 0, sizeof bit);
        int cnt = 0;
        for(int i = 0, x; i < n; ++i){
            cin >> x;
            cnt += i - query(x);
            add(x, 1);
        }

        if(cnt % 2) cout << "Marcelo\n";
        else cout << "Carlos\n";
    }
}
/**
5 1 5 3 4 2
5 5 1 3 4 2
5 1 2 3 4 5
6 3 5 2 1 4 6
5 5 4 3 2 1
6 6 5 4 3 2 1
0
**/