hdu 1394 (线段树求逆序数)

<题目链接>

题意描述：

给你一个有0--n-1数字组成的序列，然后进行这样的操作，每次将最前面一个元素放到最后面去会得到一个序列，那么这样就形成了n个序列，那么每个序列都有一个逆序数，找出其中最小的一个输出！

解题分析：

先利用线段树求出初始序列的逆序数，这里有一个非常巧妙的地方，由于比a[i]大的数是离散且连续的，所以可以用线段树来实现（与线段树节点的区间特性符合）。

#include <bits/stdc++.h>
using namespace std;

#define Lson rt<<1,l,mid
#define Rson rt<<1|1,mid+1,r
const int N = 5e3+5;
int n;
int tr[N<<2],arr[N];
inline void Pushup(int rt){ tr[rt]=tr[rt<<1]+tr[rt<<1|1]; }
void update(int rt,int l,int r,int loc){
    if(l==r){ tr[rt]+=1;return; }     //将这个点插入线段树
    int mid=l+r>>1;
    if(loc<=mid)update(Lson,loc);
    if(loc>mid)update(Rson,loc);
    Pushup(rt);
}
int query(int rt,int l,int r,int L,int R){
    if(L<=l && r<=R){ return tr[rt]; }
    int mid=l+r>>1;
    int ans=0;
    if(L<=mid)ans+=query(Lson,L,R);
    if(R>mid)ans+=query(Rson,L,R);
    return ans;
}
int main(){
    while(~scanf("%d",&n)){
        memset(tr,0,sizeof(tr));
        int sum=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&arr[i]);
            sum+=query(1,0,n-1,arr[i]+1,n-1);     //逆序数之前插入的，比这个数要大的数的个数
            update(1,0,n-1,arr[i]);
        }
        //此时ans为原序列的逆序数
        int ans=sum;
        for(int i=1;i<=n-1;i++){        //只用重新算n-1次就行，因为第n次与原序列相同 
            sum+=(n-1-2*arr[i]);        //注意这里求逆序数，必须是在前一个序列的基础上求 
            ans=min(ans,sum);
        }
        printf("%d
",ans);
    }
}