首页 > 代码库 > 求排列的逆序数之树状数组
求排列的逆序数之树状数组
代码实现
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int num[100001];
int n,a[100001];
long long count=0;
void add(int x){
for(int i=x;i<=n;i+=(i&-i))num[i]++;
}
void query(int p){
for(int i=p; i; i -= (i & -i))count+=num[i];
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=n;i>=1;i--){
query(a[i]);
add(a[i]);
}
cout<<count;
}
反着做,也可正着做(求此数到n的区间和)
求排列的逆序数之树状数组
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。