HDU 1394 Minimum Inversion Number (线段树，暴力）

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
    int n,a[100000],i,j,ans1,ans2;
    while (~scanf("%d",&n))
    {
        ans1=0;
        for (i=0;i<n;i++) scanf("%d",&a[i]);
        for (i=1;i<n;i++)
        for (j=0;j<i;j++)
        if (a[i]<a[j]) ans1++;
        ans2=ans1;
        for (i=0;i<n;i++)
        {
            ans1=ans1+n-2*a[i]-1;
            ans2=min(ans1,ans2);
        }
        printf("%d\n",ans2);
    }
    return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int s[50000];
struct p
{
    int x,y,su;
};p tree[1000000];
void build(int l,int r,int p)
{
    tree[p].x=l;
    tree[p].y=r;
    tree[p].su=0;
    if (l==r) return ;
    int m=(l+r)/2;
    build(l,m,2*p);
    build(m+1,r,2*p+1);
    return ;
}
int find(int l,int r,int p)
{
    if (tree[p].x==l&&tree[p].y==r) return tree[p].su;
    int m=(tree[p].x+tree[p].y)/2;
    if (l>m) return find(l,r,2*p+1);
    if (m>=r) return find(l,r,2*p);
    return find(l,m,2*p)+find(m+1,r,2*p+1);
}
void un(int pos,int i,int p)
{
    tree[p].su+=i;
    if (tree[p].x==tree[p].y) return ;
    int m=(tree[p].x+tree[p].y)/2;
    if (pos<=m) un(pos,i,2*p);
    else un(pos,i,2*p+1);
}
int main()
{
    int n,i,ans,mn;
    while (~scanf("%d",&n))
    {
        build(0,n-1,1);
        ans=0;
        for (i=0;i<n;i++) scanf("%d",&s[i]);
        for (i=0;i<n;i++)
        {
            ans+=find(s[i],n-1,1);
            un(s[i],1,1);
        }
        mn=ans;
        for (i=0;i<n;i++)
        {
            ans=ans+n-2*s[i]-1;
            mn=min(mn,ans);

        }
        printf("%d\n",mn);
    }
    return 0;
}