P1908 逆序对

- 2.2K通过
- 4.4K提交
题目提供者该用户不存在
标签云端
难度普及/提高-
时空限制1s / 128MB

提交讨论题解

题目描述

猫猫TOM和小老鼠JERRY最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。最近，TOM老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中ai>aj且i<j的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。

输入输出格式

输入格式：

第一行，一个数n，表示序列中有n个数。

第二行n个数，表示给定的序列。

输出格式：

给定序列中逆序对的数目。

输入输出样例

输入样例#1：

6

5 4 2 6 3 1

输出样例#1：

说明

对于50%的数据，n≤2500

对于100%的数据，n≤40000。

分析：树状数组的模板题，所给的正整数大小可能会比较大，所以先离散，给排序后的数分配一个序号，然后每次添加一个数，然后进行求和，所得到的是这个数前比它小的数的个数，那么可以很容易得到比它大的数的个数，累加答案即可.

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

int n,a[],re[];

struct node

{

    int v, id;

}t[];

bool cmp(node a, node b)

{

    return a.v < b.v;

}

void add(int x, int d)

{

    while (x <= n)

    {

        a[x] += d;

        x += x & (-x);

    }

}

int sum(int x)

{

    int cnt = ;

    while (x)

    {

        cnt += a[x];

        x -= x&(-x);

    }

    return cnt;

}

int main()

{

    scanf("%d", &n);

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

    {

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

        t[i].id = i;

    }

    sort(t + , t + n + , cmp);

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

        re[t[i].id] = i;

    long long ans = ;

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

    {

        add(re[i], );

        ans += i - sum(re[i]);

    }

    printf("%lld", ans);

    return ;

}

巴特西

洛谷P1908 逆序对

P1908 逆序对

最新讨论更多讨论

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章