树状数组求逆序对的个数
程序员文章站
2022-05-10 15:04:38
...
#include <iostream>
#include <cstring>
using namespace std;
#define N 1010
int c[N];
int n;
int lowbit(int i)
{
return i&(-i);
}
void insert(int i,int x)
{
for(;i<=n;i+=lowbit(i)){
c[i]+=x;
}
}
int getsum(int i)
{
int sum=0;
for(;i;i-=lowbit(i)){
sum+=c[i];
}
return sum;
}
int main()
{
while(cin>>n){
int ans=0;
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++){
int a;
cin>>a;
insert(a,1);
ans+=i-getsum(a);//统计当前序列中大于a的元素的个数
}
cout<<ans<<endl;
}
return 0;
}
推荐阅读
-
python实现将一个数组逆序输出的方法
-
JavaScript求一个数组中重复出现次数最多的元素及其下标位置示例
-
数据结构算法(数组中的逆序对)
-
php中对2个数组相加的函数
-
计算机体系结构(实验 3 使用 MIPS 指令实现求两个数组的点积 )
-
c语言将一个数组中的值按逆序重新存放。例如,原来顺序为8,6,5,4,1.要求改为1,4,5,6,8.
-
将一个数组中的值按逆序重新存放,例如,原来顺序为8,6,5,4,1.要求改为1,4,5,6,8。
-
C语言学习之将一个数组中的值按逆序重新存放。例如,原来顺序为8,6,5,4,1. 要求改为1,4,5,6,8。
-
6.5将一个数组中的值按逆序存放。例如:原来顺序为8,6,5,4,1.要求改为1,4,5,6,8
-
【剑指offer刷题】--数组中的逆序对