逆序数

逆序数

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

思路

这题可以用树状数组做个数组![图片说明](https://www.nowcoder.com/equation?tex=c_%7Bi%7D "图片标题") 表示元素 i 是否存在,为1表示存在

第i个元素X的逆序对个数就是在i前面的数并且比i大,即 c[x] ~ c[n]位置为1的个数

树状数组函数getsum(i)表示 数组![图片说明](https://www.nowcoder.com/equation?tex=%5Csum_%7B1%7D%5E%7Bi%7D%7Bci%7D "图片标题") 所以getsum(n) - getsum(x)表示c[x]到c[n]的为1的个数

代码

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pb push_back
#define pll pair<ll,ll>
#define INF 0x3f3f3f3f
const int mod = 1e9+7;
const int maxn = 10005;
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
inline int lowbit(int x){
    return x & (-x);
}
int c[100005];
int n;
void updata(int i,int j){//将i点的值更新为j
    while(i <= 100003 ){
        c[i] += j;
        i += lowbit(i);
    }
}
int getsum(int i){//求区间1~i的和
    int ans = 0;
    while(i > 0){
        ans += c[i];
        i -= lowbit(i);
    }
    return ans;
}
int main(){
     n = read();
    ll ans = 0;
    for(int i = 1 ; i <= n ;++i){
       int tmp = read();
       ans += getsum(100003) - getsum(tmp);
       updata(tmp,1);
    }
    cout<<ans<<endl;
}
算法竞赛入门课习题 文章被收录于专栏

0

全部评论
不应该是getsum(n)-getsum(temp)吧,如果是 5 1000 4 1 2 3 你的代码答案是3 正确答案是6
1 回复 分享
发布于 2020-06-03 21:22

相关推荐

不愿透露姓名的神秘牛友
06-11 13:34
offe从四面八方来:我真的没时间陪你闹了
点赞 评论 收藏
分享
07-11 22:27
中南大学 Java
程序员牛肉:学历的话没问题。但是没问题的也就只有学历了。 其实你的整体架构是正确的,博客接着干。但是项目有点过于简单了。从后端的角度上讲,你这也就是刚入门的水平,所以肯定约面试够呛。 如果你要应聘后端岗位,那你第一个项目竟然是仿写操作系统。这个你要面试官咋问你。你一定要记住一点,你简历上写的所有的东西,都是为了证明你有能力胜任当前的岗位,而不是为了证明你自己会什么。 如果你只是浅浅的做几个项目,描述也都是烂大街。技术点也都是各种混水类的配置类需求,那你就不要幻想自己能走多远。一定要保持思考,保持学习。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-24 13:40
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

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