树状数组板子题之一：poj 2299：Ultra-QuickSort（求逆序对）

Bertha 。 2024-04-17 05:55 81阅读 0赞

# 树状数组板子题之一：poj 2299：Ultra-QuickSort（求逆序对） #

[题目链接：poj 2299:Ultra-QuickSort][poj 2299_Ultra-QuickSort]

其实看似是问快排的交换总次数  
其实就是问**逆序对**的总数

开始实现不知道怎么搞，看了题解之后原来是要用到**离散化**，感觉有点神奇

代码入下：

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define ll long long
    using namespace std;
    /**主要用于离散化*/
    struct Node
    {
        
        int val;
        int pos;
    }node[500010];
    int c[500010];
    int n;
    inline int lowbit(int x)
    {
        
        return x&(-x);
    }
    int cmp(Node x,Node y)
    {
        
        if(x.val!=y.val)
            return x.val<y.val;
        else
            return x.pos<y.pos;
    }
    /**由于求逆序对的的特殊性，只需要加一，于是就只要一个参数即可*/
    void add(int x)
    {
        
        for(int i=x;i<=n;i+=lowbit(i))
        {
        
            c[i]++;
        }
    }
    ll sum(int x)
    {
        
        ll s=0;
        for(int i=x;i;i-=lowbit(i))
        {
        
            s+=c[i];
        }
        return s;
    }
    int main()
    {
        
        while(~scanf("%d",&n))
        {
        
            if(n==0)
                break;
            memset(node,0,sizeof(node));
            memset(c,0,sizeof(c));
            for(int i=1;i<=n;i++)
            {
        
                scanf("%d",&node[i].val);
                node[i].pos=i;
            }
            sort(node+1,node+n+1,cmp);
            ll cnt=0;
            for(int i=1;i<=n;i++)
            {
        
                add(node[i].pos);
                cnt+=i-sum(node[i].pos);
            }
            printf("%lld\n",cnt);
        }
        return 0;
    }

[poj 2299_Ultra-QuickSort]: http://poj.org/problem?id=2299