POJ.2299 Ultra-QuickSort (线段树 单点更新 区间求和 逆序对 离散化)

题意分析

前置技能

线段树求逆序对

离散化

1. 线段树求逆序对已经说过了，具体方法请看这里
2. 离散化
   
   有些数据本身很大，自身无法作为数组的下标保存对应的属性。
   
   如果这时只是需要这堆数据的相对属性， 那么可以对其进行离散化处理！
   
   当数据只与它们之间的相对大小有关，而与具体是多少无关时，可以进行离散化。例如：
   
   9 1 0 5 4 与 5 2 1 4 3 的逆序对个数相同。
   
   设有4个数：
   
   1234567、123456789、12345678、123456
   
   排序：123456<1234567<12345678<123456789
   
   => 1 < 2 < 3 < 4
   
   那么这4个数可以表示成：2、4、3、1

好的姿势

需要注意就是ans会爆int，long long 比较稳

#include <cstdio>

#include <algorithm>

#include <cstring>

#define maxn 500105

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#define ll long long

using namespace std;

int Sum[maxn<<2];

struct temp{

    int v;

    int pos;

}x[maxn];

int N;

bool cmp(temp a ,temp b)

{

    if(a.v<b.v) return true;

    else return false;

}

bool cmp2(temp a, temp b)

{

    return a.pos < b.pos;

}

void PushUp (int rt){

    Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];

}

void Build(int l,int r,int rt){

    if(l==r) {

        Sum[rt] = 0;

        return;

    }

    int m=(l+r)>>1;

    Build(l,m,rt<<1);

    Build(m+1,r,rt<<1|1);

    PushUp(rt);

}

void UpdatePoint(int L,int l,int r,int rt){

    if(l==r){

        Sum[rt]++;

        return;

    }

    int m=(l+r)>>1;

    if(L <= m) UpdatePoint(L,l,m,rt<<1);

    else UpdatePoint(L,m+1,r,rt<<1|1);

    PushUp(rt);

}

int Query(int L,int R,int l,int r,int rt){

    if(L <= l && r <= R){

        return Sum[rt];

    }

    int m = (l+r)>>1;

    int ANS = 0;

    if(L <= m) ANS += Query(L,R,l,m,rt<<1);

    if(R > m) ANS += Query(L,R,m+1,r,rt<<1|1);

    return ANS;

}

int main()

{

    //freopen("in.txt","r",stdin);

    while(scanf("%d",&N)!=EOF && N){

        ll sum = 0;

        memset(Sum,0,sizeof Sum);

        memset(x,0,sizeof x);

        Build(1,maxn,1);

        for(int i = 0;i<N;++i){

            scanf("%d",&x[i].v);

            x[i].pos = i+1;

        }

        sort(x,x+N,cmp);

        for(int i = 0;i<N;++i) x[i].v = i+1;

        sort(x,x+N,cmp2);

        for(int i = 0;i<N;++i){

            sum += Query(x[i].v+1,maxn,1,maxn,1);

            UpdatePoint(x[i].v,1,maxn,1);

        }

        printf("%I64d\n",sum);

    }

    return 0;

}