Minimum Inversion Number

题目链接：https://vjudge.net/problem/HDU-1394

思路

在线段树中维护每个数当前出现的次数，然后一个一个添加，每次添加前看有多少个数是大于自己的，然后加在逆序对总数上面就行。之后再循环一边，因为是把第一个放在最后面去，所以就是先减去小于自己的，然后再加上大于自己的。

代码

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N;
int arr[5050];
struct node
{
    int l,r;
    int v;
}tr[5050*4];

void pushup(int u){
    tr[u].v = tr[u*2].v + tr[u*2+1].v;
}
void build(int l,int r,int u = 1){
    tr[u] = {l,r,0};
    if(l == r) return ;
    int mid = (l+r)>>1;
    build(l,mid,u*2);
    build(mid+1,r,u*2+1);
    pushup(u);
}
void modify(int idx,int v,int u = 1){
    if(tr[u].l == idx && tr[u].r == idx) tr[u].v = 1;
    else{
        int mid = (tr[u].l + tr[u].r) >>1;
        if(idx<=mid) modify(idx,v,u*2);
        else modify(idx,v,u*2+1);
        pushup(u);
    }
}
int query(int l,int r,int u = 1){
    if(l<= tr[u].l && tr[u].r <= r) return tr[u].v;
    else{
        int mid = (tr[u].l + tr[u].r)>>1;
        int sum  = 0;
        if(l<=mid)  sum += query(l,r,u*2);
        if(r>mid) sum += query(l,r,u*2+1);
        return sum;
    }
}

int main(){
    // debug;
    ios;
    while(cin>>N){
        memset(tr,0,sizeof tr);
        build(1,N);
        for(int i = 1;i<=N;i++) cin>>arr[i],arr[i]+=1;
        int cnt = 0,res = 1e9;
        for(int i = 1;i<=N;i++){
            cnt += query(arr[i]+1,N);
            modify(arr[i],1);
        }
        for(int i = 1;i<=N;i++){
            if(arr[i]-1 >=1) cnt -= query(1,arr[i]-1);
            if(arr[i]+1 <=N) cnt += query(arr[i]+1,N);
            res  = min(res,cnt);
        }
        cout<<res<<endl;
    }

    return 0;
}