NYOJ 117 求逆序数（树状数组）

描述

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

现在，给你一个N个元素的序列，请你判断出它的逆序数是多少。

比如 1 3 2 的逆序数就是1。

输入

第一行输入一个整数T表示测试数据的组数（1<=T<=5)每组测试数据的每一行是一个整数N表示数列中共有N个元素（2〈=N〈=1000000）随后的一行共有N个整数Ai(0<=Ai<1000000000)，表示数列中的所有元素。数据保证在多组测试数据中，多于10万个数的测试数据最多只有一组。
输出

输出该数列的逆序数
样例输入

2

2

1 1

3

1 3 2
样例输出

0

1

分析：

因为题上要求的数据的值比较大，er我们的数组开不了那么大，这就要采用离散化的思想，将当前的这些数给转化了。

例如对于100 10 1000这三个数，他的逆序数是1，但是这样的话我们的数组消耗太大，他们的标志分别为1 2 3，如果我们把它定义为一个结构体，首先按照数值大小按照从小到大排序，然后按照标志大小从小到大排序，这样最后的标志序列就是2 1 3，他们的逆序数是相等的。就都按照这样的转换方式，求标志序列的逆序数就行。

#include<stdio.h>

#include<iostream>

#include<stack>

#include<string.h>

#include<stdlib.h>

#include<queue>

#include<algorithm>

using namespace std;

int e[1000009]= {0};

struct Node

{

    int num;///当前这个数的值

    int shu;///这个数是第几位数

} node[1000009];

bool cmp(Node a,Node b)///结构体排序，先按照数组大小排序，然后再按照他们是第几位数排序

{

    if(a.num!=b.num)

        return a.num<b.num;

    else

        return a.shu<b.shu;

}

int zhuan(int n)

{

    return (n&(-n));

}

void UpDate(int biao,int n )

{

    while(biao<=n)

    {

        e[biao]+=1;///数组e表示的是当前这个区间中有几个数

        biao+=zhuan(biao);

    }

}

int SUM(int n)///求得的是1~n之内的数的个数

{

    int sum=0;

    while(n>0)

    {

        sum+=e[n];

        n-=zhuan(n);

    }

    return sum;

}

int main()

{

    int T,n;

    scanf("%d",&T);

    while(T--)

    {

        memset(e,0,sizeof(e));

        memset(node,0,sizeof(node));

        long long  int ans=0;

        scanf("%d",&n);

        for(int i=0; i<n; i++)

        {

            scanf("%d",&node[i].num);

            node[i].shu=i+1;

        }

        sort(node,node+n,cmp);///结构体排序

        for(int i=0; i<n; i++)

        {

            ans+=SUM(n)-SUM(node[i].shu);

            UpDate(node[i].shu,n);

        }

        printf("%lld\n",ans);

    }

    return 0;

}

巴特西

NYOJ 117 求逆序数（树状数组）

最新文章

热门文章

巴特西

NYOJ 117 求逆序数 （树状数组）

最新文章

热门文章

NYOJ 117 求逆序数（树状数组）