hdu 1394 (线段树求逆序数)

#include<iostream>
using namespace std;
#define N 5005
struct
{
    int l, r;
    int num;
}tree[4 * N];

void creat(int i, int l, int r)           //初始化该线段树
{
    int mid = (l + r) / 2;
    tree[i].l = l;
    tree[i].r = r;
    tree[i].num = 0;
    if (l == r)
    {
        return;
    }
    creat(i * 2, l, mid);
    creat(i * 2 + 1, mid + 1, r);
}

void updata(int i, int k)
{
    if (tree[i].l == k && tree[i].r == k)
    {
        tree[i].num = 1;
        return;
    }
    int mid = (tree[i].l + tree[i].r) / 2;
    if (k <= mid)
        updata(i * 2, k);
    else
        updata(i * 2 + 1, k);
    tree[i].num = tree[i * 2].num + tree[i * 2 + 1].num;           //trees[i].num表示符合[trees[i].l,trees[i].r]区间的数的个数        
}

int getsum(int i, int k, int n)                       //这个函数不太明白怎么实现的
{
    if (k <= tree[i].l&&tree[i].r <= n)
    {
        return tree[i].num;
    }
    else
    {
        int mid = (tree[i].l + tree[i].r) / 2;
        int sum1 = 0, sum2 = 0;
        if (k <= mid)
            sum1 = getsum(i * 2, k, n);
        if (n>mid)
            sum2 = getsum(i * 2 + 1, k, n);
        return sum1 + sum2;
    }
}
int main()
{
    int n;
    while (scanf("%d", &n)>0)
    {
        int a[N];
        creat(1, 0, n - 1);
        int i;
        int ans = 0;
        for (i = 0; i<n; i++)
        {
            scanf("%d", &a[i]);
            ans += getsum(1, a[i] + 1, n - 1);           //a[i]+1~n-1代表比a[i]大的数，getsum()函数的作用是计算该序列前面有几个数比他大(因为此时只输入了它前面的数)
            updata(1, a[i]);
        }
        int minx = ans;
        for (i = 0; i<n; i++)         //总共要将n个数全部移动一次到序列的最末端
        {
            ans = ans + n - 2 * a[i] - 1;         //当a[i]由第一个变为最后一个时，要加上a[i]后面大于a[i]的数的个数，有n-1-a[i]个，要
            if (ans<minx)                    //减去a[i]后面小于a[i]的数的个数，有a[i]个（注意i是从0开始的）
                minx = ans;
        }
        printf("%d\n", minx);
    }
    return 0;
}