Poj 2299 - Ultra-QuickSort 离散化,树状数组,逆序对

Ultra-QuickSort

Time Limit: 7000MS		Memory Limit: 65536K
Total Submissions: 52306		Accepted: 19194

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

Source

Waterloo local 2005.02.05

题意：给定n个数，只能交换相邻的两个元素，至少交换几次，成为递增序列。

题解：

明显要求序列的逆序对数目。。。

对于样例：

9 1 0 5 4

我们将其排序：

0 1 4 5 9

在每个位置上初始放为1.

1 1 1 1 1

然后，从原序列开始遍历。

先到9，我们把其排好序的位置拿出，即为5。

然后统计位置5之前有多少1。

1 1 1 1 1

———— > 4个 ans+=4

然后把5号位置放为0。

1 1 1 1 0

继续操作即可。。。

这个树状数组维护即可。。。

注意开long long和原序列排序后要去重。。。

 #include<bits/stdc++.h>

 using namespace std;

 #define MAXN 500010

 #define LL long long

 int n,BIT[MAXN],a[MAXN],aa[MAXN];

 int read()

 {

     int s=,fh=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}

     while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}

     return s*fh;

 }

 int Lowbit(int o){return o&(-o);}

 void Update(int o,int o1)

 {

     while(o<=n)

     {

         BIT[o]+=o1;

         o+=Lowbit(o);

     }

 }

 int Sum(int o)

 {

     int sum=;

     while(o>)

     {

         sum+=BIT[o];

         o-=Lowbit(o);

     }

     return sum;

 }

 int main()

 {

     int tot,i,wz;

     LL ans;

     while()

     {

         n=read();if(n==)break;

         for(i=;i<=n;i++){a[i]=read();aa[i]=a[i];}

         memset(BIT,,sizeof(BIT));

         sort(a+,a+n+);

         tot=unique(a+,a+n+)-(a+);

         for(i=;i<=tot;i++)Update(i,);

         ans=;

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

         {

             wz=lower_bound(a+,a+tot+,aa[i])-a;

             ans+=(LL)Sum(wz-);

             if(BIT[wz]!=)Update(wz,-);

         }

         printf("%lld\n",ans);

     }

     fclose(stdin);

     fclose(stdout);

     return ;

 }

秒客网

Poj 2299 - Ultra-QuickSort 离散化,树状数组,逆序对

相关文章