http://acm.hdu.edu.cn/showproblem.php?pid=1394
给出一列数组,数组里的数都是从0到n-1的,在依次把第一个数放到最后一位的过程中求最小的逆序数
线段树的应用,先建树,输入一个数,查询在在树中比他大的数的个数,然后把这个数更新进树里,再输入数重复操作,类似于进栈一样,先更新进树的数下标肯定是小于后更新的
这样只求到了一个数组的逆序数,还要有依次把第一个数放到最后的得到新数组的比较,这里有一个结论;如果是0到n的排列，那么如果把第一个数放到最后，对于这个数列，逆序数是减少a[i],又增加n-1-a[i]的,就是加上n-1-2*a[i]的,再进行比较取最小的就行
code
#include<cstdio>
using namespace std;
struct point {
int l,r,sum;
};
point tree[*];
int a[];
int n;
void build(int i,int left,int right)
{
tree[i].l=left,tree[i].r=right;
tree[i].sum=;
if (left==right) return ;
int mid=(left+right)/;
build(i*,left,mid);
build(i*+,mid+,right);
}
int find(int i,int pos)
{
if (pos<=tree[i].l) return tree[i].sum;
int mid=(tree[i].l+tree[i].r)/;
int a=,b=;
if (pos<=mid)
a=find(i*,pos);
if (n->mid)
b=find(i*+,pos);
return a+b;
}
void update(int i,int pos)
{
if (pos==tree[i].l&&pos==tree[i].r)
{
tree[i].sum=;
return ;
}
int mid=(tree[i].l+tree[i].r)/;
if (pos<=mid)
update(i*,pos);
else
update(i*+,pos);
tree[i].sum=tree[i*].sum+tree[i*+].sum;
}
int main()
{
int ans,i,min;
while (~scanf("%d",&n))
{
if (n==) break;
ans=;
build(,,n-);
for (i=;i<=n;i++)
{
scanf("%d",&a[i]);
ans+=find(,a[i]+);
update(,a[i]);
}
min=ans;
for (i=;i<=n;i++)
{
ans=ans+n--*a[i];
if (ans<min)
min=ans;
}
printf("%d\n",min);
}
return ;
}