Bubble Sort (找规律)

　　通过模拟之后我们发现对于每一个位置上的数他都有一个规律，那就是先左移然后在右移。然后仔细发现可以知道，先右移的距离是前面比该数大的个数。右移就直接右移到目标位置了。然后用一个树状数组从左到右边扫边加就可以计算出答案了。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 7;
int tr[maxn], in[maxn], l[maxn], r[maxn], n;

int lb(int x){
    return x & -x;
}

void add(int adr, int val){
    while(adr <= n){
        tr[adr] += val;
        adr += lb(adr);
    }
}

int sum(int adr){
    int ret = 0;
    while(adr){
        ret += tr[adr];
        adr -= lb(adr);
    }
    return ret;
}

int main(){
    int T;scanf("%d", &T);
    for(int ncase = 1; ncase <= T; ncase ++){
        scanf("%d", &n);
        for(int i = 0; i <= n; i ++) tr[i] = 0;
        for(int i = 1; i <= n; i ++){
            scanf("%d", &in[i]);
            l[in[i]] = r[in[i]] = i;
            l[in[i]] = min(l[in[i]], sum(in[i]));
            r[in[i]] = max(r[in[i]], in[i]);
            add(in[i], 1);
        }
        printf("Case #%d:", ncase);
        for(int i = 1; i <= n; i ++) printf(" %d",r[i] - l[i] - 1);printf("
");
    }
    return 0;
}