Bubble Sort

题意：

给你一个1~n的排列,问冒泡排序过程中,数字i(1<=i<=n)所到达的最左位置与最右位置的差值的绝对值是多少

题解：

数字i多能到达的最左位置为min(s[i],i)

i为它的初始位置,s[i]为它的最终位置(因为最后是排好序,这个数是多少,就排在哪个位置,故为s[i])

那最右位置呢?

就是判断数i初始时,右边有多少个数比i小,这个就能用树状数组来求解了

循环从右到左,对于数s[i],我们只需判断它右边1~s[i]-1中有几个数即可

树状数组是从1开始，所以输入尽量也从1开始

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF=0x3f3f3f3f;

const ll LINF=0x3f3f3f3f3f3f3f3f;

#define PI(A) cout<<(A)<<endl

#define SI(N) cin>>(N)

#define SII(N,M) cin>>(N)>>(M)

#define cle(a,val) memset(a,(val),sizeof(a))

#define rep(i,b) for(int i=0;i<(b);i++)

#define Rep(i,a,b) for(int i=(a);i<=(b);i++)

#define reRep(i,a,b) for(int i=(a);i>=(b);i--)

#define dbg(x) cout <<#x<<" = "<<(x)<<endl

#define PIar(a,n) rep(i,n)cout<<a[i]<<" ";cout<<endl;

#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<" ";cout<<endl;}

const double EPS= 1e-9 ;

/*  /////////////////////////     C o d i n g  S p a c e     /////////////////////////  */

const int MAXN= 100000+ 9 ;

int s[MAXN],N,l[MAXN],r[MAXN];

//树状数组 范围是[1,n]

int bit[MAXN];

//求前i项和

int SUM(int i)

{

    int s=0;

    while(i>0)

    {

        s+=bit[i];

        i-=i&-i;

    }

    return s;

}

//bit[i]+x

void ADD(int i,int x)

{

    while(i<=MAXN)

    {

        bit[i]+=x;

        i+=i&-i;

    }

}

int main()

{

    int o;

    SI(o);

    Rep(T,1,o)

    {

        cle(bit,0);

        int ma=0;

        SI(N);

        Rep(i,1,N) SI(s[i]);

        Rep(i,1,N) l[s[i]]=min(s[i],i);

        for (int i=N;i>0;i--)

        {

            r[s[i]]=i+SUM(s[i]-1);

            ADD(s[i],1);

        }

        cout<<"Case #"<<T<<":";

        Rep(i,1,N) cout<<" "<<abs(l[i]-r[i]);

        cout<<endl;

    }

    return 0;

}