hdu 1394 Minimum Inversion Number（線段樹）

Minimum Inversion Number

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 13797 Accepted Submission(s): 8423


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

16

Author CHEN, Gaoli
Source ZOJ Monthly, January 2003

題意：輸入n,下面給出n個數，分別是0-n,順序不定，可以通過對序列進行移動，每次移動把最前面的數移到後面，問通過移動形成的序列，使得得到的逆序數最少
這題數據較小，可以普通暴力水過，當然比較正規的方法是線段樹。
題目要求求最小的逆序數。觀察數列，可以發現一個規律：將數列第一個數移動到最後一位之後，逆序數變為sum+n-1-2*a[i]。這個規律還是比較容易推的。
所以我們要做的就是求第一個數列的逆序數，其他的可以通過這個規律求得，最後找一個最小值即可。
我從別人那裡看來的解釋=_=：
先以區間[0,9]為根節點建立val都為0的線段樹,
再看看怎樣求下面序列的逆序數:
1 3 6 9 0 8 5 7 4 2
在線段樹中插入1, 插入之前先詢問區間[1,9]已插入的節點數(如果存在,必與1構成逆序) v1=0
在線段樹中插入3, 插入之前先詢問區間[3,9]已插入的節點數(如果存在,必與3構成逆序) v2=0
在線段樹中插入6, 插入之前先詢問區間[6,9]已插入的節點數(如果存在,必與6構成逆序) v3=0
在線段樹中插入9, 插入之前先詢問區間[9,9]已插入的節點數(如果存在,必與9構成逆序) v4=0
在線段樹中插入0, 插入之前先詢問區間[0,9]已插入的節點數(如果存在,必與0構成逆序) v5=4
在線段樹中插入8, 插入之前先詢問區間[8,9]已插入的節點數(如果存在,必與8構成逆序) v6=1
在線段樹中插入5, 插入之前先詢問區間[5,9]已插入的節點數(如果存在,必與5構成逆序) v7=3
在線段樹中插入7, 插入之前先詢問區間[7,9]已插入的節點數(如果存在,必與7構成逆序) v8=2
在線段樹中插入4, 插入之前先詢問區間[4,9]已插入的節點數(如果存在,必與4構成逆序) v9=5
在線段樹中插入2, 插入之前先詢問區間[2,9]已插入的節點數(如果存在,必與2構成逆序) v10=7
累加v1+……+v10 =22，這就是1 3 6 9 0 8 5 7 4 2的逆序數了.
就是一個個往線段樹中插入數，每次插入前詢問比這個數大的數有幾個。其實就是問一個區間裡插入了多少數字！

#include
#include
#define M 5005
struct tree{
	int l,r,sum;
}tree[M<<2];
int x[M];
int max(int a,int b){
	if(a>b)return a;
	else return b;
}
void build(int l,int r,int root)
{
	tree[root].l=l;
	tree[root].r=r;
	tree[root].sum=0;
	if(l==r)return;
	int mid=l+r>>1;
	build(l,mid,root<<1);
	build(mid+1,r,root<<1|1);
}
void pushup(int root){
	if(tree[root].l==tree[root].r)return;
	tree[root].sum=tree[root<<1].sum+tree[root<<1|1].sum;
}
void update(int l,int r,int root)
{
	if(tree[root].l==l&&tree[root].r==r){
		tree[root].sum++;
		return;
	}
	int mid=tree[root].l+tree[root].r>>1;
	if(r<=mid)update(l,r,root<<1);
	else if(l>mid)update(l,r,root<<1|1);
	else {
		update(l,mid,root<<1);
		update(mid+1,r,root<<1|1);
	}
	pushup(root);
}
int  query(int l,int r,int root)
{
	if(tree[root].l==l&&tree[root].r==r){
		return tree[root].sum;
	}
	int mid=tree[root].l+tree[root].r>>1;
	if(r<=mid)return query(l,r,root<<1);
	else if(l>mid)return query(l,r,root<<1|1);
	else return query(l,mid,root<<1)+query(mid+1,r,root<<1|1);
}
int main()
{
	int n,m,i,j,k,a[M],b,tot;
	while(scanf(%d,&n)!=EOF)
	{
		tot=0;
		build(0,n-1,1);
		for(i=0;i