HDU 5775 树状数组

Bubble Sort

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

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

题意：冒泡排序中求每一个位置的上的数移动的最左端与最右端的距离差值

题解：因为在冒泡排序中，每次都将序列中最小的数向前移动，所以位置i上的数只会与在它之后的并小于它的数交换

树状数组倒序遍历求求小于i位置数的个数x 所有最右端为r=i+x;对于左边界l=min(原位置,升序排列之后的位置);

但是注意此题中的n个数都是不同的

可以这么想,在一次冒泡过程中,只有当前未排序的最大元素才有可能向右移动,其余元素均会向左移动;

那么一个元素ai 的最左端位置为l= i-num(左端比ai大的数的个数) r=max(原位置,升序排列之后的位置）

两种思路都是可以的代码是按照第二种写的的

另外,刚开始有一个错误的思路

两次使用树状数组,记录ai左边大于ai的个数xl，ai右边小于的ai的个数xr

l=i-xl; r=i+xr

hack 数据

5 4 2 3 1

 1 /******************************
 2 code by drizzle
 3 blog: www.cnblogs.com/hsd-/
 4 ^ ^    ^ ^
 5  O      O
 6 ******************************/
 7 //#include<bits/stdc++.h>
 8 #include<iostream>
 9 #include<cstring>
10 #include<cstdio>
11 #include<map>
12 #include<algorithm>
13 #include<queue>
14 #include<cmath>
15 #define ll __int64
16 #define PI acos(-1.0)
17 #define mod 1000000007
18 using namespace std;
19 #define NN 100000
20 int tree[100005];
21 int t;
22 int n;
23 int a[100005];
24 struct node
25 {
26     int l;
27     int r;
28 } N[100005],MM[100005];
29 struct pan{
30  int v;
31  int pos;
32 }M[100005];
33 bool cmp(struct pan aa,struct pan bb)
34 {
35     return aa.v<bb.v;
36 }
37 int lowbit(int t)
38 {
39     return t&(-t);
40 }
41 void add(int i,int v)
42 {
43     for(; i<=NN; i+=lowbit(i))
44         tree[i]+=v;
45 }
46 int sum(int i)
47 {
48     int ans=0;
49     for(; i>0; i-=lowbit(i))
50         ans+=tree[i];
51     return ans;
52 }
53 int main()
54 {
55     while(~scanf("%d",&t))
56     {
57         for(int i=1; i<=t; i++)
58         {
59             scanf("%d",&n);
60             for(int j=1; j<=n; j++)
61             {
62                 scanf("%d",&a[j]);
63                 M[j].pos=j;
64                 M[j].v=a[j];
65                 N[j].l=j;
66                 N[j].r=j;
67             }
68             for(int j=0; j<=n; j++)
69                 tree[j]=0;
70             for(int j=1; j<=n; j++)
71             {
72                 add(a[j],1);
73                 N[j].l=N[j].l-(j-sum(a[j]));
74             }
75             sort(M+1,M+1+n,cmp);
76             for(int j=1;j<=n;j++)
77                 N[M[j].pos].r=max(j,N[M[j].pos].r);
78             for(int j=1;j<=n;j++)
79             {
80                 MM[a[j]].l=N[j].l;
81                 MM[a[j]].r=N[j].r;
82             }
83             for(int j=1; j<=n; j++)
84             {
85                 if(j==1)
86                     printf("Case #%d: %d",i,MM[j].r-MM[j].l);
87                 else
88                     printf(" %d",MM[j].r-MM[j].l);
89             }
90             printf("
");
91         }
92     }
93     return 0;
94 }