传送门

描述

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.

输入

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.

输出

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

样例

• Input
  10
  1 3 6 9 0 8 5 7 4 2
• Output
  16

思路

• 题意：给n个数，范围是0~n-1，并且每个数出现一次，每次可以将第一个数移到最后，求最大的逆序数（前面比他大的数的个数）之和
• 将a[i]填入对应位置，然后求1到a[i]中已经出现的数(这些数都小于等于a[i])的个数p，则a[i]的逆序数为i-p。当然这种方法的空间占用为max(a[i])，最好还是先离散化：，然后求出初始的逆序数和sum。
• ，因为每个数的范围是0~n-1且只出现一次，所以当a[i]从第一个位移到最后一位时，后面比他小的数的逆序数-1，逆序数和sum就要-(a[i])，自身的逆序数要加上整个序列里比他大的数，也就是(n-1)-a[i]，所以sum+=n-1-a[i]-a[i];
• 单点修改区间查询

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

#include
         
           #include
          
            #include
           
             #define LL long long #define INIT(a,b) memset(a,b,sizeof(a)) using namespace std; struct Tree{
         	int num,k,l,r; }tree[20001]; int a[5001],sum,ans; void build(int l,int r,int d){
        	tree[d]=(Tree){
        0,0,l,r}; 	if(l==r)return ; 	int mid=(tree[d].l+tree[d].r)/2; 	build(l,mid,d<<1); 	build(mid+1,r,d<<1|1); } void add(int i,int a,int d){
        	if(tree[d].l==tree[d].r){
        		tree[d].num+=a; 		return; 	} 	int mid=(tree[d].l+tree[d].r)/2; 	if(i<=mid)add(i,a,d<<1); 	else add(i,a,d<<1|1); 	tree[d].num=tree[d<<1].num+tree[d<<1|1].num; } int find(int l,int r,int d){
        	if(tree[d].l==l&&tree[d].r==r) 		return tree[d].num; 	int mid=(tree[d].l+tree[d].r)/2; 	if(r<=mid) return find(l,r,d<<1); 	else if(mid