Bubble Sort (找规律)

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

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + ;

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 = ;

    while(adr){

        ret += tr[adr];

        adr -= lb(adr);

    }

    return ret;

}

int main(){

    int T;scanf("%d", &T);

    for(int ncase = ; ncase <= T; ncase ++){

        scanf("%d", &n);

        for(int i = ; i <= n; i ++) tr[i] = ;

        for(int i = ; 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], );

        }

        printf("Case #%d:", ncase);

        for(int i = ; i <= n; i ++) printf(" %d",r[i] - l[i] - );printf("\n");

    }

    return ;

}