HDU 1394(Minimum Inversion Number)

题目大意：给你一个连续的自然数序列，
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)

中逆序数最大的是多少。

其实用树状数组求这个是非常方便速度的，但是为了锻炼线段树  我还是用线段树写了。

程序+部分注释：

#include<iostream>
#include<stdio.h>
using namespace std;
int ans=0;
struct node{
	int a,b;
	int v;
}s[20000];

int t[5002];

int Build(int x,int y,int num){
	s[num].a=x;	s[num].b=y;
	s[num].v=0;
	if(x==y)
		return 0;
	Build(x,(s[num].a+s[num].b)/2,num+num);
	Build((s[num].a+s[num].b)/2+1,y,num+num+1);	
}

int modify(int num,int ide ){
	if(s[num].a==s[num].b){
		s[num].v=1;
		return 0;
	}
	else{
		if(ide<=(s[num].a+s[num].b)/2)
			modify(num+num,ide);
		else if(ide>(s[num].a+s[num].b)/2)
			modify(num+num+1,ide);
		s[num].v=s[num+num].v+s[num+num+1].v;
	}
}

int getsum(int x,int y,int num){
	if(x==s[num].a&&y==s[num].b){
		ans+=s[num].v;
		return 0;
	}
	else{
		if(y<=(s[num].a+s[num].b)/2)
			getsum(x,y,num+num);
		else if(x>(s[num].a+s[num].b)/2)
			getsum(x,y,num+num+1);
		else{
			getsum(x,(s[num].a+s[num].b)/2,num+num);
			getsum((s[num].a+s[num].b)/2+1,y,num+num+1);
		}
	}
}

int main(){
	int n,i,min;
	while(scanf("%d",&n)!=EOF){
		ans=0;
		for(i=1;i<=n;i++)
			scanf("%d",&t[i]);
		Build(1,n,1);
		for(i=n;i>=1;i--){
			getsum(1,t[i]+1,1);
			modify(1,t[i]+1);
                        求出总和
		}
		min=ans;
		for(i=1;i<=n-1;i++){
			ans=ans-t[i]+n-t[i]-1;
                        //因为数组是连续的自然数，从0到n所以
                       //t[i]移动到最后面去，就减少了t[i]个逆                    
                         //序对，同时也与以前是后面的而且比他大的数构成了
                           //N-（t[i]+1）组逆序对
			if(ans<min)
				min=ans;
		}
		printf("%d\n",min);
	}
	return 0;
}