P1908 逆序对-（树状数组）

2020-12-13 16:27

阅读：449

标签：style 记录 inf lin color str text scanf double

https://www.luogu.org/problem/P1908

比较喜欢线段树，懒得用树状数组（只会套模板，位运算的精髓没有领悟到），一直没有记录树状数组代码，又得捡回来，趁这道题记录一下模板，为三维偏序cdq套树状数组铺垫一下。

解题思路：先对原数组a从大到小排序，依次添加进树状数组c里，每次求前缀和的结果就是当前数的逆序对的个数。

例如数据：55，44，22，66，33，11

初始化树状数组c，清0；

添加66到4号位，则添加数组为 0，0，0，1，0，0； 66前没有比它大的数，逆序对个数为0，树状数组C为0，0，0，1，0，0；

添加55到1号位，则添加数组为 1，0，0，1，0，0； 55前没有比它大的数，逆序对个数为0，树状数组C为1，1，0，2，0，0；

添加44到2号位，则添加数组为 1，1，0，1，0，0； 44前有55比它大，逆序对个数为1，树状数组C为1，2，0，3，0，0

添加33到5号位，则添加数组为 1，1，0，1，1，0； 33前有55，44，66比它大，逆序对个数为3，树状数组C为1，2，0，3，1，1

添加22到3号位，则添加数组为 1，1，1，1，1，0； 22前有55，44，66比它大，逆序对个数为2，树状数组C为1，2，1，4，1，2

添加11到6号位，则添加数组为 1，1，1，1，1，1； 11前有55，44，22，66，33比它大，逆序对个数为5，树状数组C为1，2，1，4，1，2

坑：如果有相同的数，则排序时按照后面的先添加，这样就不会重复计算逆序对。

#include
#include
#include
#include
#include
#includestring>
#include
#include
#include
#includeset>
#include#define ll long long
#define inf 0x3f3f3f3f
const double pi=3.1415926;
using namespace std;

const int maxx=500005;
struct node
{
    int id;
    int val;
};
node a[maxx];///原数组
int c[maxx];///树状数组
int n;

bool cmp(node p1,node p2)
{
    if(p1.val==p2.val)///坑
        return p1.id>p2.id;
    return p1.val>p2.val;
}

int lowbit(int x)
{
    return x&(-x);
}

void add(int x,int val)///在x的位置添加val值
{
    while(x1)///x需要小于32005，否则，那些输入x=20000的大数据没办法找到左下的行星数量
    {
        c[x]+=val;
        x+=lowbit(x);
    }
}

int sum(int x)
{
    int res=0;
    while(x>0)
    {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}



int main()///P1908
{
    scanf("%d",&n);
    for(int i=1;i)
        scanf("%d",&a[i].val),a[i].id=i;
    sort(a+1,a+n+1,cmp);
    ll ans=0;
    for(int i=1;i)
    {
        ans +=(ll)sum(a[i].id);
        add(a[i].id,1);
    }
    printf("%lld\n",ans);
    return 0;
}

P1908 逆序对-（树状数组）

标签：style 记录 inf lin color str text scanf double

原文地址：https://www.cnblogs.com/shoulinniao/p/11619715.html

上一篇：python基础数据类型一(元祖)

下一篇：直接插入排序/二分插入排序/希尔排序

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：P1908 逆序对-（树状数组）
文章链接：http://soscw.com/essay/36163.html

亲，登录后才可以留言！

P1908 逆序对-（树状数组）

评论

热门文章

推荐文章

最新文章

置顶文章