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
?
|