HDU 5775 Bubble Sort(线段树)(2016 Multi-University Training Contest 4 1012)

原址地址：http://ibupu.link/?id=31

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的序列，问序列中每个数在冒泡排序过程中的极右下标与极左下标的差

思路是查询当前数的右侧比其小的个数，然后判断当前位置+右侧比其小的个数比最终位置小还是大，大的话当前位置+右侧比其小的个数就是极右下标，否则最终位置就是极右下标。极左下标是判断当前位置比最终位置小还是大，当前位置就是极左下标，否则最终位置是极左下标。因为是排序，所以最终位置就是当前数。

查询当前数右侧比其小的个数用到了线段树，在本题线段树除了存放区间中数的个数外，叶子结点还可以一一对应1到N的节点。

就3 1 2这个样例来说，我们对序列从右向左开始遍历查询。

一开始的时候，线段树初始化为空

第一步，我们查询2右侧比其小的个数，那么就是在线段树中查询区间1到1，而现在线段树中为空，那么，查询到的结果就是0；然后我们将2插入线段树，线段树中2所对应的节点变成了1，并对上面的父节点+1。

第二步，我们来查询1右侧比其小的个数，但是因为1是最小的所以不用查询了，值为0；我们将1插入线段树，线段树中1所对应的节点变成了1，并对上面的父节点+1。

第三步，我们来查询3右侧比其小的个数，那么就是在线段树中查询区间1到2，区间节点对应的值为2；我们将3插入线段树，线段树中3所对应的节点变成了1，并对上面的父节点+1。

这样就找到了1，2，3的右侧比其小的个数分别是0，0，2。

/*bupu*/

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <string>

#include <cmath>

#include <map>

#define N 100005

#define LLU unsigned long long

#define LL long long

#define INF 1999999

#define MAX(a,b) (a>b?a:b)

#define MIN(a,b) (a<b?a:b)

#define lson s,mid, i << 1

#define rson mid+1,t, i << 1 | 1

using namespace std;

int a[N],b[N],cont[N],trie[4*N],Max[N],Min[N];

void putup(int i)

{

    trie[i] = trie[i<<1] + trie[i<<1|1];

}

void Update(int left,int right,int s,int t,int i)

{

    if(left <= s && t <= right)

    {

        trie[i] = 1;

        return;

    }

    int mid = (s+t) >> 1;

    if(left<= mid)

        Update(left,right,lson);

    else if(mid < right)

        Update(left,right,rson);

    putup(i);

}

int Query(int left,int right,int s,int t,int i)

{

    if(left <= s && t <= right)

    {

        return trie[i];

    }

    int mid = (s+t)>>1;

    long long ret = 0;

    if(left <= mid)

        ret += Query(left,right,lson);

    if(mid < right)

        ret += Query(left,right,rson);

    return ret;

}

int main()

{

    int T,n,t = 1;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        memset(trie,0,sizeof(trie));

        memset(cont,0,sizeof(cont));

        for(int i = 1; i <= n; i++)

        {

            scanf("%d",&a[i]);

            b[a[i]] = i;

        }

        for(int i = n; i >= 1; i--)

        {

            if(a[i] > 1)

                cont[a[i]] += Query(1,a[i]-1,1,n,1);

            Update(a[i],a[i],1,n,1);

        }

        for(int i = 1; i <= n; i++)

        {

            if(b[i]+cont[i] >= i)

                Max[i] = b[i]+cont[i];

            else

                Max[i] = i;

            if(b[i] < i)

                Min[i] = b[i];

            else

                Min[i] = i;

        }

        printf("Case #%d: %d",t++,Max[1] - Min[1]);

        for(int i = 2; i <= n; i++)

        {

            printf(" %d",Max[i] - Min[i]);

        }

        puts("");

    }

    return 0;

}

巴特西