参考:http://blog.sina.com.cn/s/blog_691ce2b70101ldmm.html
https://blog.csdn.net/wiking__acm/article/details/7920429
语法:https://zhidao.baidu.com/question/172532047.html
#include <stdio.h>
#include <algorithm> using namespace std; int a[];
struct Node{
int l,r,num;//num该区间已出现数的个数
}tree[]; void Build(int n,int x,int y){
tree[n].l = x;
tree[n].r = y;
tree[n].num = ;
if(x == y){
return;
}
int mid = (x + y) / ;
Build(*n,x,mid);
Build(*n+,mid+,y);
} void Modify(int n,int x){//在输入的相应叶节点加1
int l = tree[n].l;
int r = tree[n].r;
int mid = (l + r) / ;
if(x == l && x == r){
tree[n].num = ;
return;
}
if(x <= mid) Modify(*n,x);
else Modify(*n+,x);
tree[n].num = tree[*n].num + tree[*n+].num;
} int Query(int n,int x,int y){//求大于该数且已经出现的数个数,n节点序号,x左端点,y右端点
int l = tree[n].l;
int r = tree[n].r;
int mid = (l + r) / ;
int ans = ;
if(x == l && y == r)
return tree[n].num;
if(x <= mid) ans += Query(*n,x,min(mid,y));
if(y > mid) ans += Query(*n+,max(mid+,x),y);
return ans;
}
int main(){
int n,sum,ans;
int i,j; while(scanf("%d",&n) != EOF){
sum = ;
Build(,,n-);//区间端点取0~n-1即可
for(i = ;i <= n;i++){
scanf("%d",&a[i]);
Modify(,a[i]);
sum += Query(,a[i]+,n-);
}
ans = sum;
for(i = ;i < n;i++){
sum = sum + (n - - a[i]) - a[i];//根据递推式加上接下来依次循环的序列的逆序数
if(sum < ans)
ans = sum;//要最小的
}
printf("%d\n",ans);
}
}