Bubble Sort

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Problem Description

P is a permutation of the integers from 1 to N(index starting from 1).
Here is the code of Bubble Sort in C++.


for(int i=1;i<=N;++i)
    for(int j=N,t;j>i;—j)
        if(P[j-1] > P[j])
            t=P[j],P[j]=P[j-1],P[j-1]=t;

After the sort, the array is in increasing order. ?? wants to know the absolute values of difference of rightmost place and leftmost place for every number it reached.

Input

The first line of the input gives the number of test cases T; T test cases follow.
Each consists of one line with one integer N, followed by another line with a permutation of the integers from 1 to N, inclusive.

limits
T <= 20
1 <= N <= 100000
N is larger than 10000 in only one case.

Output

For each test case output “Case #x: y1 y2 … yN” (without quotes), where x is the test case number (starting from 1), and yi is the difference of rightmost place and leftmost place of number i.

Sample Input

3 1 2

1 2 3

Sample Output

Case #1: 1 1 2

Case #2: 0 0 0

题意：问冒泡排序的过程中每个数最右位置和最左位置的差是多少;

思路：

一个数a[i]最左的位置为min(i,a[i]);最右的位置为：若其后有x个它大的数max(a[i],n-x);x可以由n-a[i]-逆序数得到;就是树状数组求一下逆序数;

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <bits/stdc++.h>
#include <stack>

using namespace std;

#define For(i,j,n) for(int i=j;i<=n;i++)
#define mst(ss,b) memset(ss,b,sizeof(ss));

typedef  long long LL;

template<class T> void read(T&num) {
    char CH; bool F=false;
    for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar());
    for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar());
    F && (num=-num);
}
int stk[70], tp;
template<class T> inline void print(T p) {
    if(!p) { puts("0"); return; }
    while(p) stk[++ tp] = p%10, p/=10;
    while(tp) putchar(stk[tp--] + '0');
    putchar('
');
}

const LL mod=20071027;
const double PI=acos(-1.0);
const int inf=1e9;
const int N=4e5+10;
const int maxn=500+10;
const double eps=1e-8;


int sum[N],ans[N],a[N],n;
int lowbit(int x)
{
    return x&(-x);
}
void update(int x)
{
    while(x)
    {
        sum[x]++;
        x-=lowbit(x);
    }
}
int query(int x)
{
    int s=0;
    while(x<=n)
    {
        s+=sum[x];
        x+=lowbit(x);
    }
    return s;
}


int main()
{       
        int t,Case=0;
        read(t);
        while(t--)
        {
            mst(sum,0);
            read(n);
            For(i,1,n)read(a[i]);
            int l,r;
            For(i,1,n)
            {
                l=min(i,a[i]);
                 r=a[i]+query(a[i]);
                 update(a[i]);
                ans[a[i]]=r-l;
            }
            printf("Case #%d: ",++Case);
            For(i,1,n-1)printf("%d ",ans[i]);printf("%d
",ans[n]);
        }    
        return 0;
}