HDU 1394 线段树单点更新求逆序数

题意：给出含有0 ~n-1 N个数组成的序列，有N次操作，每次把第一个数放到数列的最后，问这几次数列操作中最小的逆序数的值。

单点更新就可以，每一输入一个数，先查询有几个比这个数大的，再将这个值插入线段树中。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 5005
struct  node
{
    int l,r,val;
};
node tree[N<<2];
int num[N];
void build(int root,int l,int r)
{
    tree[root].l=l;
    tree[root].r=r;
    tree[root].val=0;
    if(l==r)
        return;
    int mid=(l+r)>>1;
    build(root<<1,l,mid);
    build(root<<1|1,mid+1,r);
}
void update(int root,int pos,int val)
{
    if(tree[root].l==tree[root].r)
    {
        tree[root].val=val;
        return;
    }
    int mid=(tree[root].l+tree[root].r)>>1;
    if(pos<=mid)
        update(root<<1,pos,val);
    else
        update(root<<1|1,pos,val);
    tree[root].val=tree[root<<1].val+tree[root<<1|1].val;
}
int query(int root,int l,int r)
{
    if(l<=tree[root].l&&r>=tree[root].r)
        return tree[root].val;
    int mid=(tree[root].l+tree[root].r)>>1,ret=0;
    if(l<=mid)
        ret+=query(root<<1,l,r);
    if(r>mid)
        ret+=query(root<<1|1,l,r);
    return ret;
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        build(1,1,n);
        int sum=0;
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&num[i]);
            sum+=query(1,num[i]+1,n-1);
            update(1,num[i],1);
        }
        int ans=1e8;
        for(int i=1; i<=n; i++)
            sum=sum-num[i]+(n-num[i]-1),ans=min(ans,sum);
        printf("%d\n",ans);
    }
    return 0;
}