题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1394
线段树功能:update:单点增减 query:区间求和
分析：如果是0到n-1的排列，那么如果把第一个数放到最后，对于这个数列，逆序数是减少a[i],而增加n-1-a[i]的，所以每次变化为res+=n-a[i]-1-a[i].
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define maxn 5555
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
int sum[maxn<<];
int a[maxn];
void PushUp(int rt)
{
sum[rt]=sum[rt<<]+sum[rt<<|];
}
void build(int l,int r,int rt)
{
sum[rt]=;
if(l==r)
return;
int m=(r+l)>>;
build(lson);
build(rson);
}
void update(int pos,int l,int r,int rt)
{
if(r==l)
{
sum[rt]++;
return;
}
int m=(r+l)>>;
if(pos<=m)update(pos,lson);
else update(pos,rson);
PushUp(rt);
}
int Query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
return sum[rt];
}
int m=(r+l)>>;
int res=;
if(L<=m)res+=Query(L,R,lson);
if(m<R)res+=Query(L,R,rson);
return res;
}
int main()
{
int n;
while(scanf("%d",&n)>)
{
build(,n-,);
int sum=;
for(int i=;i<n;i++)
{
scanf("%d",&a[i]);
sum+=Query(a[i],n-,,n-,);
update(a[i],,n-,);
}
int ans=sum;
for(int i=;i<n;i++)
{
sum+=n-a[i]-a[i]-;
ans=min(ans,sum);
}
printf("%d\n",ans);
}
return ;
}
树状数组求逆序对更简单。。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define maxn 5555
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
int a[maxn],c[maxn];
int n;
int lowbit(int x)
{
return x&(-x);
}
int sum(int i)
{
int res=;
while(i)
{
res+=c[i];
i-=lowbit(i);
}
return res;
}
void update(int i,int x)
{
while(i<=n)
{
c[i]+=x;
i+=lowbit(i);
}
}
int main()
{
while(scanf("%d",&n)>)
{
int res=;
memset(c,,sizeof(c));
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
a[i]++;
res+=i--sum(a[i]);//求1~a[i]区间的出现的数，再总（i-1）-sum(a[i])即可
update(a[i],);//单点更新
}
int ans=res;
for(int i=;i<=n;i++)
{
res+=n-a[i]-(a[i]-);
ans=min(ans,res);
}
printf("%d\n",ans);
}
}