首页 > 代码库 > Ultra-QuickSort (树状数组离散化)

Ultra-QuickSort (树状数组离散化)

题目原意是用归并排序,刚学树状数组,就用了下

树状数组的离散化

离散化,是数据范围太大是所借用的利器,举个例子,有四个数99999999 1 123 1583 数据范围太大,而树状数组中的c数组开的范围是数据的范围,这时候就需要离散化,把四个数一次标号为1 2 3 4(即第一个数,第二个数。。。),按键值排序之后 依次为2 3 4 1(即从小到大排序为第二个数,第三个数。。。),所以,第二个数是最小的,即f[2]=1,f[3]=2,f[4]=3,f[1]=4,也就是把键值变为了1~n,相对大小还是不变的,即4  1 2 3。

用f[]数组存放相对大小,要引用原数组第i个的元素,就是f[i]


题目给的数据有maxn=500000,完全逆序的逆序数为等差数列的前n项和=(maxn-1)*maxn/2   , 差不多是10的13次方,所以要用longlong


#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define maxn 500010
typedef long long LL;
using namespace std;
struct node
{
    int x,i;
}a[maxn];
int n;
int c[maxn],f[maxn];
bool cmp(node x,node y)
{
    return x.x<y.x;
}
int lowbit(int x)
{
    return x&-x;
}
void update(int x,int v)
{
    while(x<=n){
        c[x]+=v;
        x+=lowbit(x);
    }
}

int getsum(int x)
{
    int sum=0;
    while(x>0){
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
int main()
{
    while(~scanf("%d",&n),n){
        memset(c,0,sizeof(c));
        memset(f,0,sizeof f);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i].x);
            a[i].i=i;//在原数组的下标
        }
        sort(a+1,a+n+1,cmp);//开始离散化
        f[a[1].i]=1;//从最小的开始
        for(int i=2;i<=n;i++){
            if(a[i].x!=a[i-1].x){
                f[a[i].i]=i;
            }
            else f[a[i].i]=f[a[i-1].i];
        }//离散化结束
        LL ans=0;
        for(int i=1;i<=n;i++){
            update(f[i],1);
            ans+=i-getsum(f[i]);//第i个数的逆序数=i-前面有多少个比它小的=就是前面多少个比它大的  ,getsum(i)就是前面有多少个数比i小
        }                       //也能写成 ans+=getsum(n)-getsum(i)
        cout<<ans<<endl;
    }
    return 0;
}