poj2299--B - Ultra-QuickSort（线段树，离散化）

Ultra-QuickSort

Time Limit: 7000MS		Memory Limit: 65536K
Total Submissions: 41215		Accepted: 14915

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

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999,
the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

Output

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

Sample Input

Sample Output

6

0

题意：求出最小交换次数。使得数组变得有序（由小到大）。也就是求出逆序数。这个题归并排序，树状数组。线段树又能够解，能够当做练手用

使用线段树解的话，由于给出的数值非常大。所以须要离散化。一開始直接使用map果断的超时了，仅仅能想一个更简便的离散的方法，使用结构体存下一開始的值k和它初始的序号（id1），sort对k进行排序。得到新的序号（id2），通过id1直接改变给出的数组。变为id2。这样仅仅用n + logn的时间就能够离散完毕，（注意要推断反复的值。反复的值共享一个id2）。至于线段树部分就是一个模板

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define LL __int64

#define maxn 600000

#define lmin 1

#define rmax n

#define lson l,(l+r)/2,rt<<1

#define rson (l+r)/2+1,r,rt<<1|1

#define root lmin,rmax,1

#define now l,r,rt

#define int_now LL l,LL r,LL rt

struct node{

    LL id1 , id2 ;

    LL k ;

}p[maxn] ;

LL cl[maxn<<2] , a[maxn] ;

bool cmp(node a,node b)

{

    return a.k < b.k ;

}

void push_up(int_now)

{

    cl[rt] = cl[rt<<1] + cl[rt<<1|1] ;

}

void update(LL i,int_now)

{

    if( i < l || i > r )

        return ;

    if( i == l && i==r )

    {

        cl[rt]++ ;

        return ;

    }

    update(i,lson);

    update(i,rson);

    push_up(now);

    return ;

}

LL query(int ll,int rr,int_now)

{

    if( ll > r || rr < l )

        return 0;

    if( ll <= l && r <= rr )

        return cl[rt] ;

    return query(ll,rr,lson) + query(ll,rr,rson);

}

int main()

{

    LL i , n , m , l , r , x , num ;

    while(scanf("%I64d", &m) && m)

    {

        for(i = 0 ; i < m ; i++)

        {

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

            p[i].k = a[i] ;

            p[i].id1 = i ;

        }

        sort(p,p+m,cmp);

        int temp = -1 ;

        n = 0 ;

        for(i = 0 ; i < m ; i++)

        {

            if( p[i].k == temp )

                p[i].id2 = n ;

            else

            {

                p[i].id2 = ++n ;

                temp = p[i].k ;

            }

        }

        for(i = 0 ; i < m ; i++)

            a[ p[i].id1 ] = p[i].id2 ;

        memset(cl,0,sizeof(cl));

        num = 0 ;

        for(i = 0 ; i < m ; i++)

        {

            num += (i - query(1,a[i],root));

            update(a[i],root);

        }

        printf("%I64d\n", num);

    }

    return 0;

}

秒客网

poj2299--B - Ultra-QuickSort（线段树，离散化）

相关文章