POJ 2299 Ultra-QuickSort

去年第一次看到这个马桶塞 是俱乐部介绍归并排序的时候 当初也写了很久 这里就不说了

现在暑假集训 放在树状数组专题 没多久就有了想法

但是以下算法适合应对数据较小的题目 此题不适合 可看可不看

假如以我们一个人的思维求逆序数 我们会计算在它后面的 而且比它小的数字的个数sum 所以我们只要从末尾开始计算 在n位置的前n-1项的sum 就能一个不漏计算出这个位置的逆序数

以样例为例 9 1 0 5 4 先全部初始化为0

1.先计算4 前面全为0 得0

2.计算5 前面有一个4 得1

3.计算0 前面全为0 得0

4.计算1 前面有一个0 得1

5.计算9 前面有0,1 4 5 得4

所有相加的答案 6

结果就是RE了 因为 a[i]的范围是小于等于999,999,999 以上算法必须开这么大的数组 所以RE 不行

没办法 只能去看了题解 看到有指出离散化的思想 卧靠 我完全不懂 又小补了一下离散化 这里就不说了

如果要离散化上述算法 我想是应该将 9 1 0 5 4 想办法 转化成 5 2 1 4 3 但是又要排序又要还原 我就懵逼了

下面是我看的题解思路

开一个结构体记录 下标pos和数值val 以val升序排序 再开个数组 记录排序后的下标

eg

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>
#include <stack>

using namespace std;
int n,maxn;
const int key=500010;

struct node
{
    int val;
    int pos;
};

node nodes[key];
int kao[key],reflect[key];

bool cmp(const node& a, const node& b)
{
    return a.val < b.val;
}
int lowbit(int a)
{
    return a&(-a);
}

void add(int x,int num)
{
    while(x<=n)
    {
        kao[x]+=num;
        x+=lowbit(x);
    }
}

int getsum(int x)
{
    int sum=0;
    while(x)
    {
        sum+=kao[x];
        x-=lowbit(x);
    }
    return sum;
}

int main()
{
    while(scanf("%d",&n),n)
    {
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &nodes[i].val);
            nodes[i].pos = i;
        }
        sort(nodes + 1, nodes + n + 1, cmp);
        for (int i = 1; i <= n; i++)
            reflect[nodes[i].pos] = i;
        for (int i = 1; i <= n; i++)
            kao[i] = 0;
        long long ans = 0;
        for (int i = 1; i <= n; i++)
        {
            add(reflect[i],1);
            ans += (i - getsum(reflect[i]));
        }
        printf("%lld\n", ans);
    }
    return 0;
}