[原创]HDU 5775 Bubble Sort [树状数组]【数据结构】

2016-11-08 21:03:47 Tabris_ 阅读数：233

博客爬取于2020-06-14 22:42:45
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/53088409

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5775

----------------------------------------------------------.
Bubble Sort

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

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.

Author
FZU

Source
2016 Multi-University Training Contest 4

-----------------------------------------------------------.

题目大意：
就是求每个数字在冒泡排序的过程中位置的区间大小

解题思路：
用手写了写 发现结果就是
max（前面有几个比a_i大，后面有几个比a_i小）；
其实也很好想 根据冒泡排序的交换规则
很容易的计算每一个数字左移数和右移数
至于结果为什么是二者的最大值 也很好想,
因为两者的差就是a_i-i,画图演示的话就是
这里写图片描述
其他情况得跟这个差不多 不再赘述/

然后用树状数组维护两遍就行了

附本题代码
---------------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# include <bits/stdc++.h>

# define abs(x)          (((x)>0)?(x):-(x))
# define lalal           puts("*********")
# define Rep(a,b,c)      for(int a=(b);a<=(c);a++)
# define Req(a,b,c)      for(int a=(b);a>=(c);a--)
# define Rop(a,b,c)      for(int a=(b);a<(c);a++)
# define s1(a)           scanf("%d",&a)
using namespace std;
/**************************************/

const int N = 100000+5;
# define lowbit(x)  (x&-x)
int sum[N],cnt,ans[N],a[N];
void update(int index,int val){
    for(int i=index;i<=cnt;i+=lowbit(i))
        sum[i]+=val;
    return;
}

int getSum(int index){
    int ans = 0;
    for(int i=index;i>0;i-=lowbit(i))
        ans+=sum[i];
    return ans;
}

int main(){
    int _,kc,x;
    while(~s1(_)){
        kc=0;
        while(_--){
            s1(cnt);
            memset(sum,0,sizeof(sum));
            memset(ans,0,sizeof(ans));
            Rep(i,1,cnt){
                s1(a[i]);
                ans[a[i]] =getSum(cnt)-getSum(a[i]);
                update(a[i],1);
            }
            memset(sum,0,sizeof(sum));
            Req(i,cnt,1){
                ans[a[i]] =max(ans[a[i]],getSum(a[i]));
                update(a[i],1);
            }
            printf("Case #%d:",++kc);
            Rep(i,1,cnt) printf(" %d",ans[i]);
            puts("");
        }
    }
    return 0;
}