逆序数

逆序数

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

树状数组简单应用,逆序数转换为:求前i个数小于x的和。

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
using namespace std;

typedef long long ll;
const int maxn=2e5+10;
int sum[maxn],cnt=maxn-1;

void add( int x ) { while( x<=cnt ) sum[x]++,x+=lowbit(x); }
int query( int x ,int ans=0 ) { while( x ) ans+=sum[x],x-=lowbit(x);return ans; }  

int main()
{
    int n;
    cin>>n;
    ll ans=0;
    for( int i=1;i<=n;i++ ) 
    {
        int x;cin>>x;x=1e5+10-x;
        ans+=query(x-1);
        add(x);
    }
    cout<<ans<<endl;
}

全部评论

相关推荐

就只能3个月,但是要求长期全职实习
Swaying:你确实是能长期实习啊,但是你那时候有事也没啥办法嘛
点赞 评论 收藏
分享
Ncsbbss:又想干活又想要工资,怎么什么好事都让你占了
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
5
收藏
分享

创作者周榜

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