学步园

求Inversion的最小逆序数

先用线段树求出初序列的逆序数，

然后 每次将最后一个数，移到第一个位置

逆序数的变化  减少a[i],  增加n - 1 - a[i]

记录最小逆序数

update:单点增减 query:区间求和

#include <cstdio>
#include <cstring>
using namespace std;

#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
const int maxn = 5005;
struct node 
{
    int l, r;
    int sum;
}tree[maxn*4];
int a[maxn];

void build(int rt, int l, int r) 
{
    tree[rt].l = l;
    tree[rt].r = r;
    tree[rt].sum = 0;
    if(tree[rt].l == tree[rt].r) {
        return ;
    }
    int mid = (tree[rt].l + tree[rt].r)>>1;
    build(LL(rt), l, mid);
    build(RR(rt), mid+1, r);
}
void update(int rt, int pos)
{
    if(tree[rt].l == tree[rt].r) {
        tree[rt].sum += 1;
        return ;
    }
    int mid = (tree[rt].l + tree[rt].r)>>1;
    if(pos <=mid) update(LL(rt), pos);
    else update(RR(rt), pos);
    tree[rt].sum = tree[LL(rt)].sum + tree[RR(rt)].sum;
}
int  query(int rt, int l, int r) 
{
    if(l <= tree[rt].l && tree[rt].r <= r) {
        return tree[rt].sum;
    }
    int mid = (tree[rt].l + tree[rt].r)>>1;
    int ret = 0;
    if(l <= mid) ret += query(LL(rt), l, r);
    if(r > mid)  ret += query(RR(rt), l, r);
    return ret;
}
int main()
{
    int n, i, ret, sum;
    while(scanf("%d",&n)!=EOF)
    {
        build(1, 0, n-1);
        sum = 0;
        for(i=0; i<n; ++i) {
            scanf("%d",&a[i]);
            sum += query(1, a[i], n-1);
            update(1,a[i]);
        }
        ret = sum;
        for(i=0; i<n-1; ++i) {
            ret += n- a[i] - a[i] - 1;
            if(sum > ret) sum = ret;
        }
        printf("%d\n", sum);
    }
    return 0;
}