题目的意思就好比给出一个序列
如：0 3 4 1 2
设逆序数初始n = 0；
由于0后面没有比它小的，n = 0
3后面有1,2 n = 2
4后面有1,2,n = 2+2 = 4；
所以该序列逆序数为 4
或者这样想
先输0 前面没有比它大的 n = 0
3也没有 4也没有
1前面 3 4 比它大 n += 2
2前面 3 4 比它大 n += 2
n = 4
其根据题意移动产生的序列有
3 4 1 2 0 逆序数：8
4 1 2 0 3 逆序数：6
1 2 0 3 4 逆序数：2
2 0 3 4 1 逆序数：4
所以最小逆序数为2
Sample Input
10
1 3 6 9 0 8 5 7 4 2
Sample Output
16
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <cmath>
# include <queue>
# define LL long long
using namespace std ; const int maxn = ; int sum[maxn<<] ; //结点开4倍
int x[maxn] ; void PushUP(int rt) //更新到父节点
{
sum[rt] = sum[rt * ] + sum[rt * + ] ; //rt 为当前结点
} void build(int l , int r , int rt) //构建线段树 所有点都置零
{
sum[rt] = ;
if (l == r)
{
return ;
}
int m = (l + r) / ;
build(l , m , rt * ) ;
build(m + , r , rt * +) ; } void updata(int p , int l , int r , int rt) //单点增
{
if (l == r)
{
sum[rt]++ ;
return ;
}
int m = (l + r) / ;
if (p <= m)
updata(p , l , m , rt * ) ;
else
updata(p , m + , r , rt * + ) ;
PushUP(rt) ;
} int query(int L , int R , int l , int r , int rt) //区间求和
{
if (L <= l && r <= R)
return sum[rt] ;
int m = (l + r) / ;
int ret = ;
if (L <= m)
ret += query(L , R , l , m , rt * ) ;
if (R > m)
ret += query(L , R , m + , r , rt * + ) ;
return ret ;
} int main ()
{
//freopen("in.txt","r",stdin) ;
int n ;
while(scanf("%d" , &n) != EOF)
{
build( , n - , ) ; //因为序列里有0 所以要从0开始
int sum = ;
int i ;
for (i = ; i < n ; i++)
{
scanf("%d" , &x[i]) ;
sum += query(x[i] , n- , , n- , ) ; //sum累加的是 现在输入的x[i] 和 之前输入的数相比 有几个比它大 也就是逆序
updata(x[i] , , n- , ) ;
}
int ret = sum ; //当前输入序列的逆序
for (i = ; i < n ; i++) //每次循环 都是将之前的序列的第一位以移到最后一位
{
sum += n - x[i] - x[i] - ; //sum为移动后的逆序
ret = min(ret , sum) ;
}
printf("%d\n" , ret) ;
} return ;
}