hdu 1394 Minimum Inversion Number（线段树 单点更新)
题目大意：
给由0-n-1这n个数构成的n个数，定义一个逆序数（前面的比后面的大的数的个数）。把第一个数移到最后的位置，得到一个新的序列，得到一个新的逆序数。一共可以移动n-1次，得到n个逆序数，问这n个逆序数最小的是多少。
解题思路：
1、先求出第一个序列的逆序数。
根据题目特点，建立一个0——(n-1)的线段树，每个区间保存含有当前区间内数的个数。
对每一个数，查找该数到n-1内已存在数的个数，（因为该数前面的所有数都压到线段树里面去了），再把该数压进去。
把每个数前面的逆序数加起来，就可以构造出整个逆序数。
2、当把第一个移到最后时，后面有0——(save[1]-1)一共save[1]个数比save[i]小，共有n-1-save[1]个数比save[1]大
所以得到递推公式，sum=sum-save[i]+(n-1-save[i])。
代码：
[cpp]
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#define eps 1e-6
#define INF (1<<20)
#define PI acos(-1.0)
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,(rt<<1)|1
#define maxn 5100
int sum[4*maxn],save[maxn];
void build(int l,int r,int rt)
{
sum[rt]=0; //表示该区间一共有多少个数
if(l==r)
return ;
int m=(l+r)>>1;
build(lson);
build(rson);
return ;
}
int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&R>=r) //如果要找区间大于当前区间，直接返回当前区间
return sum[rt];
int m=(l+r)>>1,temp=0;
if(R<=m)
return query(L,R,lson);
else if(L>m)
return query(L,R,rson);
else
{
temp+=query(L,R,lson);
temp+=query(L,R,rson);
return temp;
}
}
void pushup(int rt) //向上更新，每次插入的时候向上更新，注意是覆盖
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int target,int l,int r,int rt)
{
if(l==r)
{
sum[rt]++;
return ;
}
int m=(l+r)>>1;
if(target<=m)
update(target,lson);
else
update(target,rson);
pushup(rt);
return ;
}
int main()
{
int n,temp;
while(scanf("%d",&n)!=EOF)
{
int sum=0;
build(0,n-1,1); //注意区间是0-(n-1)
for(int i=1;i<=n;i++)
{
scanf("%d",&save[i]);
sum+=query(save[i],n-1,0,n-1,1);
update(save[i],0,n-1,1);
}
int ans=sum;
for(int i=1;i<n;i++)
{
sum+=n-2*save[i]-1;
ans=min(sum,ans);
}
printf("%d\n",ans);
}
return 0;
}
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#define eps 1e-6
#define INF (1<<20)
#define PI acos(-1.0)
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,(rt<<1)|1
#define maxn 5100
int sum[4*maxn],save[maxn];
void build(int l,int r,int rt)
{
sum[rt]=0; //表示该区间一共有多少个数
if(l==r)
return ;
int m=(l+r)>>1;
build(lson);
build(rson);
return ;
}
int query(int L,int R,int l,int r,int rt)
{
if(L<=l&&R>=r) //如果要找区间大于当前区间，直接返回当前区间
return sum[rt];
int m=(l+r)>>1,temp=0;
if(R<=m)
return query(L,R,lson);
else if(L>m)
return query(L,R,rson);
else
{
temp+=query(L,R,lson);
temp+=query(L,R,rson);
return temp;
}
}
void pushup(int rt) //向上更新，每次插入的时候向上更新，注意是覆盖
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int target,int l,int r,int rt)
{
if(l==r)
{
sum[rt]++;
return ;
}
int m=(l+r)>>1;
if(target<=m)
update(target,lson);
&
补充：软件开发 , C++ ,
