题目链接：

题意：

让你找每一个数在冒泡排序中最右边和最左边的位置的差值

题解：

还是官方题解，讲的已经很清楚了

1012 Bubble Sort

考虑一个位置上的数字c在冒泡排序过程的变化情况。c会被其后面比c小的数字各交换一次，之后c就会只向前移动。数组从右向左扫，树状数组维护一下得到每个值右边有多少个比其小的值，加上原位置得到最右位置，最左位置为初始位置和最终位置的最小值。

 

时间复杂度O(n lg n)

1 #include
      
        2 #define mst(a,b) memset(a,b,sizeof(a)) 3 #define F(i,a,b) for(int i=a;i<=b;++i) 4 using namespace std; 5  6 const int N=1e5+7; 7 int ans[N],sum[N],n; 8 inline void add(int x,int c){
    while(x<=n)sum[x]+=c,x+=x&-x;} 9 inline int ask(int x){
    int an=0;while(x)an+=sum[x],x-=x&-x;return an;}10 11 int main(){12     int t,ic=1,tp;13     scanf("%d",&t);14     while(t--)15     {16         mst(sum,0);17         scanf("%d",&n);18         F(i,1,n)19         {20             scanf("%d",&tp);21             int mi=tp-ask(tp-1)-1;22             add(tp,1);23             ans[tp]=i+mi-min(tp,i);24         }25         printf("Case #%d:",ic++);26         F(i,1,n)printf(" %d",ans[i]);puts("");27     }28     return 0;29 }