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
101 3 6 9 0 8 5 7 4 2Sample Output
16来源： http://acm.hdu.edu.cn/showproblem.php?pid=1394大意：给出一个从0到n-1的序列，逐次把首数字移到尾部，问，最小逆序数？
题解：
这里的逆序数和线性代数中的逆序数是一个概念，某个数前面出现比其大的数，称为逆序，总序列中逆序的个数，称为逆序数。用线段树求第一次输入的序列的逆序数，然后用公式来遍历所有转移情况。
#include#include #include #include #define M 5001using namespace std;struct Node{ int a; int b; int sum;}t[3*M];int p[M],total;/* 创建范围为x~y的线段树 */ void make(int x,int y,int n){ t[n].a = x; t[n].b = y; t[n].sum = 0; if(x != y){ int mid = (x + y)/2; make(x,mid,2*n); make(mid+1,y,2*n+1); } }/* 返回 x~y 区间内的个数sum */int query(int x,int y,int n){ if(x <= t[n].a && y >= t[n].b){ return t[n].sum; }else{ int mid = (t[n].a + t[n].b)/2; if(x > mid){ query(x,y,2*n+1); }else if( y <= mid){ query(x,y,2*n); }else{ return query(x,y,2*n)+query(x,y,2*n+1); } }}/* 从最高级区间开始往下面的具有x的区间的sum */ void update(int x,int n){ t[n].sum++; if(t[n].a == x && t[n].b == x){ return; } int mid = (t[n].a + t[n].b)/2; if(x > mid){ update(x,2*n+1); }else{ update(x,2*n); }}int main(){ int n,m,a[M]; while(~scanf("%d",&n)){ make(0,n-1,1); int total = 0; for(int i=0;i