POJ 2299 Ultra-QuickSort （树状数组求逆序数 || 线段树 +离散化）

小鱼儿 2024-02-17 21:21 62阅读 0赞

Ultra-QuickSort

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 7000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 60319</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 22343</td> 
  </tr> 
 </tbody> 
</table>

Description

![2299_1.jpg][]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

5
    9
    1
    0
    5
    4
    3
    1
    2
    3
    0

Sample Output

6
    0

分析：就是求逆序数，对每一个元素找到它后面小于它的个数，即当前数对应的逆序数，所有的相加即可。当然需要用的离散化的知识，元素值的范围0~999 999 999数组开不下。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    typedef long long LL; 
    const int maxn=5e5+10;
    struct node{
    	int v,pos;
    }p[maxn];
    
    int C[maxn];
    int a[maxn];
    int N;
    
    bool cmp(const node& n1,const node& n2){
    	return n1.v<n2.v;
    }
    
    int lowbit(int i){
    	return i&-i;
    }
    
    void update(int i){
    	while(i<=N){
    		C[i]++;
    		i+=lowbit(i);
    	}
    }
    
    int sum(int i){
    	int cnt=0;
    	while(i){
    		cnt+=C[i];
    		i-=lowbit(i);
    	}
    	return cnt;
    }
    
    int main(){
    	while(scanf("%d",&N)==1 && N){
    		memset(C,0,sizeof(C));
    		
    		for(int i=1;i<=N;i++){
    			scanf("%d",&p[i].v);
    			p[i].pos=i;
    		}
    		
    		sort(p+1,p+N+1,cmp);
    		
    		for(int i=1;i<=N;i++) //离散化 
    		a[p[i].pos]=i;
    		
    		LL cnt=0;
    		for(int i=N;i>=1;i--){
    			update(a[i]); 
    			cnt+=sum(a[i]-1);
    		}
    		printf("%lld\n",cnt);
    	}
    	return 0;
    }

方法二：线段树求解 ：思路就是，先离散化，然后从后向前更新树，将值设置为1，然后求逆序数（也就是求和，有多少个1，该节点就对应有多少个逆序数）。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    typedef long long LL;
    const int maxn=5e5+10;
    int sum[maxn<<2];
    int a[maxn];
    int N;
    
    struct node{
    	int v,pos;
    }p[maxn];
    
    bool cmp(const node& n1,const node& n2){
    	return n1.v<n2.v;
    }
    
    void build(int l,int r,int rt){
    	sum[rt]=0; 
    	if(l==r){
    		return ;
    	}
    	int m=l+(r-l)/2;
    	build(l,m,rt<<1);
    	build(m+1,r,rt<<1|1);
    }
    
    void Update(int i,int l,int r,int rt){
    	if(r==l){
    		sum[rt]=1;
    		return ;
    	}
    	int m=l+(r-l)/2;
    	if(i<=m)
    	Update(i,l,m,rt<<1);
    	else 
    	Update(i,m+1,r,rt<<1|1);
    	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    }
    
    int Query(int i,int j,int l,int r,int rt){
    	if(i<=l&&j>=r){
    		return sum[rt];
    	}
    	int m=l+(r-l)/2;
    	int ans=0;
    	if(i<=m)
    	ans+=Query(i,j,l,m,rt<<1);
    	if(j>m)
    	ans+=Query(i,j,m+1,r,rt<<1|1);
    	return ans;
    }
    
    int main(){
    	while(scanf("%d",&N)==1 && N){
    		
    		for(int i=1;i<=N;i++){
    		  scanf("%d",&p[i].v);
    		  p[i].pos=i;
    		}
    		
    		sort(p+1,p+N+1,cmp);
    		
    		for(int i=1;i<=N;i++) //离散化 
    		a[p[i].pos]=i;
    		
    		build(1,N,1);
    		
    		LL cnt=0;
    		for(int i=N;i>=1;i--){
    			Update(a[i],1,N,1);
    			cnt+=Query(1,a[i],1,N,1)-1;
    		}
    		
    		printf("%lld\n",cnt);
    	} 
    	return 0;
    }

[2299_1.jpg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/8d2a27f7f5514b839354756519710b43.png