【HDU5775】 Bubble Sort 多校 树状数组 统计数组中某个数右边小于这个数的个数详解_树状数组 求右边比自己小的数的数量 c++

Bubble Sort

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2605    Accepted Submission(s): 1255

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

2 
3 
3 1 2 
3 
1 2 3

Sample Output

Case #1: 1 1 2 
Case #2: 0 0 0

Hint

In first case, (3, 1, 2) -> (3, 1, 2) -> (1, 3, 2) -> (1, 2, 3) the leftmost place and rightmost place of 1 is 1 and 2, 2 is 2 and 3, 3 is 1 and 3 In second case, the array has already in increasing order. So the answer of every number is 0.

题意：就是有一个数组要进行冒泡排序，某个数在冒泡排序中出现在最左边的位置和最右边的位置之差的最大值。

题解：我们先分析一下这个数在最左边的位置，只有两种情况，一是它自己本身在数据中的那个位置，二是它本来在上升序列中应该出现的位置，最小的那个值就是它出现在最左边的那个位置。最右边的位置是它本身在数据中的位置+右边比他小的数的个数，为什么是小的数的个数呢，读者不妨想一下，因为冒泡排序把小的那个数往前移，所以某个数右边比他小的个数的每一个都会移到这个数的前面，所以这个数会向后移的距离为比他小的数的个数。所以通式为 ans=i+d-min(i,a[i]-1)。现在要解决的问题是怎么计算某个数右边的比他小的个数，树状数组，可以用来计数。要是读者懂树状数组的话，我们可以想一下，比如我们要统计某个数右边小于他的个数，我们将数逆序插入树状数组就看当前在这个数之前插入树状数组的数比这个小的数的个数，这个不难想到。因为最后一个数肯定右边没有比他更小的数，这时树状数组就是空的。我们就实时逆序插入，我们每插入一个数，就看在树状数组中这个数位置的前面有多少个数，因为比他小的数一定会插到这个数的前面，所以我们直接将权值赋值为1，通过求和就能知道这个数前面有多少个数，也就说在数组中这个数的右边有多少个比这个数小的数的个数。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=100000+7;
int a[maxn];
int b[maxn];
int tree[maxn<<1];
int T,n;
int lowbit(int x)   
{
    return x&-x;
}
int add(int x,int v)   //更新结点
{
    while(x<=n){
        tree[x]+=v;
        x+=lowbit(x);
    }
    return 0;
}
int getsum(int x)   //求和
{
    int ans=0;
    while(x>0){
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
}
int main()
{
    scanf("%d",&T);
    for(int t=1;t<=T;t++){
        memset(tree,0,sizeof(tree));
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        for(int i=n-1;i>=0;i--){  //因为最右边的那个数的后面不可能有比它还小的数
            int x=getsum(a[i]);   //计算a[i]右边比a[i]小的元素的个数
            //因为它统计的是在这个数前面有多少个数 即比他小而且又提前插入
            add(a[i],1);   //出现了a[i]就在a[i]对应的位置+1代表这个数出现一次
            b[a[i]]=i+x-min(i,a[i]-1);  //i+x：数据中的位置+右边比这个数小的个数
        }  //右边的比这个数小的个数就是它要往后移动的距离
        //min(i,a[i]-1)  最左边的话 要么它数组中的位置最左 要么它正确对应的位置最左
        printf("Case #%d: ",t);
        for(int i=1;i<=n;i++){
            if(i==1)printf("%d",b[i]);
            else printf(" %d",b[i]);
        }
        printf("\n");
    }
    return 0;
}