逆序数

逆序数

https://ac.nowcoder.com/acm/problem/15163

树状数组模板题、归并也行

树状数组,先查询树状数组内当前有多少个数比当前的数字大,然后再把数字更新上去即可。。

#include<bits/stdc++.h>
using namespace std;
int c[1<<17];
int n;
void add(int x){
    for(;x<=n;x+=x&-x) c[x]++;
}
int get(int x){
    int ans=0;
    for(;x;x-=x&-x) ans+=c[x];
    return ans;
}
int main(){
    cin>>n;
    long long ans=0;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        ans += get(n)-get(x);
        add(x);
    }
    cout<<ans;
    return 0;
}
全部评论
树状数组c数据类型应该是long long,int范围太小。get应该返回类型应该是long long,
点赞 回复 分享
发布于 2023-01-29 15:50 浙江
层主方法错了几个地方,第一没考虑输入的数有可能为0,而树状数组要求下标从0开始。第二add那里也有问题,n并不一定是数组的范围。
点赞 回复 分享
发布于 2023-01-29 15:46 浙江
应该是get(100000)-get(x),add的时候x<=100000才对,hack数据5 50 40 30 20 10,这题数据弱
点赞 回复 分享
发布于 2022-01-18 10:41

相关推荐

06-25 16:00
武汉大学 Java
工科研究生底薪工资就开3k啊??
机械打工仔:写文章提成的岗位工资低,你怪工科?
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-26 15:18
点赞 评论 收藏
分享
仁者伍敌:难怪小公司那么挑剔,让你们这些大佬把位置拿了
点赞 评论 收藏
分享
能干的三文鱼刷了10...:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
评论
7
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务