POJ 2299 Ultra-QuickSort 求逆序数 线段树或树状数组 离散化

我用的线段树写的。

num数组表示已插入的数值的个数。

由于a[i]数值很大，但是n不是很大，所以要离散化处理

9 1 0 5 4

离散化后

4 1 0 3 2

这样保证最大值不会超过n

#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;

typedef long long ll;
const int MAXN = 543210;
int a[MAXN], mp[MAXN], num[MAXN<<2];

void push_up(int rt)
{
    num[rt] = num[rt<<1] + num[rt<<1|1];
}

void update(int p, int l, int r, int rt)
{
    if(l == r)
    {
        num[rt]++;
        return;
    }
    int m = (l + r) >> 1;
    if(p <= m) update(p, lson);
    else update(p, rson);
    push_up(rt);
}

int query(int L, int R, int l, int r, int rt)
{
    if(L <= l && r <= R) return num[rt];
    int m = (l + r) >> 1;
    int ret = 0;
    if(L <= m) ret += query(L, R, lson);
    if(R > m) ret += query(L, R, rson);
    return ret;
}

bool cmp(int A, int B)
{
    return a[A] < a[B];
}

int main()
{
//    freopen("in.txt", "r" ,stdin);
    int n;
    while(~scanf("%d", &n) && n)
    {
        for(int i=0; i<n; i++)
        {
            scanf("%d", &a[i]);
            mp[i] = i;
        }
        //离散化，排序后处理
        sort(mp, mp+n, cmp);    //离散化排序
        for(int i=0; i<n; i++)
            a[mp[i]] = i;       //离散化处理
        ll ans = 0;
        memset(num, 0, sizeof(num));
        for(int i=0; i<n; i++)
        {
            ans += query(a[i], n-1, 0, n-1, 1);
            update(a[i], 0, n-1, 1);
        }
        printf("%I64d
", ans);
    }
    return 0;
}