Minimum Inversion Number(线段树经典例题：逆序对)

布满荆棘的人生 2022-04-23 16:24 127阅读 0赞

Problem Description

The inversion number of a given number sequence a1, a2, ..., an is the number of pairs (ai, aj) that satisfy i < j and ai > aj.  
  
For a given sequence of numbers a1, a2, ..., an, if we move the first m >= 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following:  
  
a1, a2, ..., an-1, an (where m = 0 - the initial seqence)  
a2, a3, ..., an, a1 (where m = 1)  
a3, a4, ..., an, a1, a2 (where m = 2)  
...  
an, a1, a2, ..., an-1 (where m = n-1)  
  
You are asked to write a program to find the minimum inversion number out of the above sequences.

Input

The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 5000); the next line contains a permutation of the n integers from 0 to n-1.

Output

For each case, output the minimum inversion number on a single line.

Sample Input

10 1 3 6 9 0 8 5 7 4 2

Sample Output

#include<bits/stdc++.h>
    using namespace std;
    struct Node{int l,r,v;}t[200005];
    int n,a[6000];
    void build(int k,int l,int r){
    	t[k].v=0; 
    	t[k].l=l;
    	t[k].r=r;
    	if(l==r){
    		return ;
    	}
    	int mid=(l+r)/2;
    	build(k*2,l,mid);
    	build(k*2+1,mid+1,r);
    }
    int query(int k,int l,int r){
    	if(l<=t[k].l&&t[k].r<=r)return t[k].v;
    	int res=0,mid=(t[k].l+t[k].r)/2;
    	if(l<=mid)res+=query(k*2,l,r);
    	if(mid<r)res+=query(k*2+1,l,r);
    	return res;
    }
    void update(int k,int x){
    	if(t[k].l==x&&t[k].r==x){
    		t[k].v++;
    		return ;
    	}//将这个加 1 
    	int mid=(t[k].l+t[k].r)/2;
    	if(x<=mid)update(k*2,x);//如果是左孩子 
    	if(x>mid)update(k*2+1,x);//如果是右孩子 
    	t[k].v=t[k*2].v+t[k*2+1].v;//更新父亲 
    }
    int main(){
    	while(~scanf("%d",&n)){//文件输入结束 
    		int res=0,ans;
    		build(1,0,n-1);
    		for(int i=1;i<=n;i++){ //按照要求输入 
    			scanf("%d",&a[i]);
    			res+=query(1,a[i],n-1);//前面比他大的有多少 
    			update(1,a[i]);//将这个数据入队 
    		}
    		ans=res;
    		for(int i=1;i<=n;i++){
    			ans+=n-a[i]*2-1;
    			res=min(res,ans);
    		}
    		printf("%d\n",res);
    	}
    	return 0;
    }