poj 2299 线段树

Description

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is
sorted in ascending order. For the input sequence 
9 1 0 5 4 ,

Ultra-QuickSort produces the output 
0 1 4 5 9 .

Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

Input

Output

Sample Input

5
9
1
0
5
4
3
1
2
3
0

Sample Output

6
0

转化为线段树：

我们先将原数组每个值附上一个序号index，再将它排序。如题目的例子：

num：   9  1  0  5  4
index：  1  2  3  4  5

排序后：

num：   0  1  4  5  9
index：  3  2  5  4  1

然后由于排序后num为0的点排在原来数组的第3个，所以为了将它排到第一个去，那就至少需要向前移动两次，同时它也等价于最小的数0之前有2个数比它大（所以要移动两次），将0移到它自己的位置后，我们将0删掉（目的是为了不对后面产生影响）。再看第二大的数1，它出现在原数组的第二个，他之前有一个数比它大所以需要移动一次。这样一直循环下去那么着5个数所需要移动的次数就是：

num：  0  1  4  5  9
次数      2  1  2  1  0

将次数全部要加起来就是最后所需要移动的总次数

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;

const int maxx=500010;
#define LL long long
int sum[maxx<<2];

struct record
{
    int value;
    int pos;
}a[maxx];

bool cmp(record x,record y)
{
    return x.value>y.value;
}

//------------------------------------//
void build(int p,int l,int r)
{
    sum[p]=0;
    if(l==r)
        return ;

    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}
//------------------------------------//

void update(int p,int l,int r,int m)
{
    sum[p]++;
    if(l==r)
        return ;

    int mid=(l+r)>>1;
    if(m<=mid)
        update(p<<1,l,mid,m);
    else
        update(p<<1|1,mid+1,r,m);
}

//------------------------------------//

int query(int p,int l,int r,int left,int right)
{
    if(left==l&&r==right)
        return sum[p];

    int mid=(l+r)>>1;
    if(right<=mid)
        return query(p<<1,l,mid,left,right);
    else if(left>mid)
        return query(p<<1|1,mid+1,r,left,right);
    else
        return query(p<<1,l,mid,left,mid)+query(p<<1|1,mid+1,r,mid+1,right);
}

//------------------------------------//
int main()
{
    int n;
    //freopen("in.txt","r",stdin);
    while(scanf("%d",&n),n)
    {
        build(1,1,n);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            a[i].pos=i+1;
        }
        sort(a,a+n,cmp);

        LL ans=0;
        for(int i=0;i<n;i++){
            update(1,1,n,a[i].pos);
            if(a[i].pos==1)
                continue;
            ans+=query(1,1,n,1,a[i].pos-1);
        }
        printf("%I64d\n",ans);
    }
    return 0;
}