hdu 5775 Bubble Sort (树状数组)

Bubble Sort

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

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.

题意是给出一个由1~n组成的序列,求出模拟冒泡排序时,每个数能到达的最左位置和最右位置的差。

暴力找下规律,会发现一个数右移的次数是右边比这个数小的数的个数,所以右边的位置是当前位置加上后面比这个数小的数的个数。左边位置是排完序后的位置与一开始所在的位置中更小的那个。求右边比这个数小的数的个数用树状数组,类似白书例题LA 4329的做法。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int C[maxn];
int n;

inline int lowbit(int x) {
    return x & (-x);
}

int sum(int x) {
    int ret = 0;
    while(x > 0) {
        ret += C[x]; x -= lowbit(x);
    }
    return ret;
}

void add(int x, int d) {
    while(x <= maxn) {
        C[x] += d; x += lowbit(x);
    }
}

int a[maxn];
int r[maxn], l[maxn];
int id[maxn];

int main() {
    int t;
    scanf("%d", &t);
    int cas = 0;
    while(t--) {
        memset(C, 0, sizeof(C));
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);

        for(int i = n; i >= 1; i--) {
            add(a[i], 1);
            r[i] = sum(a[i] - 1);
            id[a[i]] = i;
        }

        //for(int i = 1; i <= n; i++) printf("%d ", r[i]); puts("");
        vector<int> ans;
        for(int i = 1; i <= n; i++) {
            int ll = min(id[i], i);
            int rr = id[i] + r[id[i]];
            //printf("check %d %d %d\n", i, ll, rr);
            ans.push_back(rr - ll);
        }
        printf("Case #%d:", ++cas);
        for(int i = 0; i < ans.size(); i++) {
            printf(" %d", ans[i]);
        }puts("");
    }
}
时间: 07-27

hdu 5775 Bubble Sort (树状数组)的相关文章

HDU 5775 L - Bubble Sort 树状数组

给定一段冒泡排序的代码,要求输出每个数字能到达的最右边的位置和最左边的位置的差 因为那段冒泡排序的代码是每次选取一个最小的数,放在左边的,所以,每个数最多能到达右边的位置应该是起始位置i+右边有多少个数比它大. 它能到达的最左的位置,可以这样考虑 1.它本来应该是排去起始位置的左边的,就是它本来是一个小的数字,起始位置在末尾这种情况的话.最左边的值就是a[i] 2.它是去右边的,那么最左边的值就是起始位置, 两种取max就去可以了 #include <cstdio> #include <

HDU 3333 Turing Tree 树状数组 离线查询

题意: 给你一个数列,然后有n个查询,问你给定区间中不同数字的和是多少. 思路还是比较难想的,起码对于蒟蒻我来说. 将区间按照先右端点,后左端点从小到大排序之后,对于每个查询,我只要维护每个数字出现的最后一次就可以了(这个结论稍微想一下就可以证明是正确的). 然后就是简单的点更新,区间求和问题了- #include <cstdio> #include <cstring> #include <iostream> #include <map> #include

HDU 1541 Stars (树状数组)

Problem Description Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given

HDU 3854 Glorious Array(树状数组)

题意:给一些结点,每个结点是黑色或白色,并有一个权值.定义两个结点之间的距离为两个结点之间结点的最小权值当两个结点异色时,否则距离为无穷大.给出两种操作,一种是将某个结点改变颜色,另一个操作是询问当前距离小于K的结点有多少对,K是一个定值. 思路:先求最初时候小于k的结点有多少对,然后每次改变颜色的时候,统计该点左侧和右侧各有多少同色和异色的结点(这一步使用树状数组),分别处理就行.另外需要预处理离某个结点最近的两个距离小于K的结点的位置. 代码写的略乱. #include<cstdio> #

HDU 2492 Ping pong (树状数组)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2492 Ping pong Problem Description N(3<=N<=20000) ping pong players live along a west-east street(consider the street as a line segment). Each player has a unique skill rank. To improve their skill rank

hdu 5775 Bubble Sort(2016 Multi-University Training Contest 4——树状数组)

题目链接: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): 636    Accepted Submission(s): 378 Problem Description P is a permutation of the

HDU 3333 Turing Tree (树状数组)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3333 题意就是询问区间不同数字的和. 比较经典的树状数组应用. 1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstrin

hdu 3333 Turing Tree (树状数组+离线处理+离散化)

Turing Tree Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3981    Accepted Submission(s): 1349 Problem Description After inventing Turing Tree, 3xian always felt boring when solving problems a

HDU 5101 Select --离散化+树状数组

题意:n 组,每组有一些值,求 在不同的两组中每组选一个使值的和大于k的方法数. 解法:n * Cnt[n] <= 1000*100 = 100000, 即最多10^5个人,所以枚举每个值x,求他的后面那些组中有多少数大于 k-x即可, 求有多少数大于k-x可以先求有多少数小于等于k-x,然后总数减一下即可. 可以用树状数组求. 先把所有数离散地存入一个树状数组中,然后每次枚举完一组的数后,将这组的数去掉. 代码: #include <iostream> #include <cst