树状数组是一种能快速求出前n项和的数据结构,
例如:数组a0,a1,a2,a3,a4,a5....an。
sum(a[4])求的就是a0+a1+a2+a3+a4。
sum(a[n]-a[4])求的就是a5+...+an。
时间复杂度为o(nlogn)。
离散化 就是把原来的一组数变成另一组数,但是他们的相对大小不变。比如
把 4 6 8 9 2
变成 2 3 4 5 1
他们的逆序数不变
下面贴代码:
#include<iostream> #include<cmath> #include<string.h> #include<algorithm> using namespace std; const int MAXN=1000000+5; int b[MAXN],c[MAXN]; int n; struct node { int num,id; }a[MAXN]; bool cmp(node a,node b) { return(a.num<b.num); } void add(int i)//更新树状数组 { while(i<=n) { c[i]++; i+=i&(-i); } } int sum(int i)//树状数组求和 { int totle; while(i>0) { totle+=c[i]; i-=i&(-i); } return(totle); } int main() { int i,T; __int64 ans; scanf("%d",&T); while(T--) { scanf("%d",&n); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); for(i=1;i<=n;i++) { scanf("%d",&a[i].num);//记录数据 a[i].id=i;//记录是第几个输入的 } sort(a+1,a+n+1,cmp); b[a[1].id]=1;//最小的那个变成1,次小的那个变成2,以此类推... for(i=2;i<=n;i++) { if(a[i].num!=a[i-1].num) b[a[i].id]=i; else b[a[i].id]=b[a[i-1].id]; } ans=0; for(i=1;i<=n;i++) { add(b[i]); ans+=(__int64)(sum(n)-sum(b[i]));//求到目前为止比这个数大的有多少个 } printf("%I64d\n",ans); } return(0); }
相关推荐
逆序数c++源码,直接运行
广工《算法和高级数据结构教程》 逆序对(树状数组) c语言实现
统计数组中的逆序对的个数,基于归并排序的思想,先拆分为单个元素,再合并为两个元素的数组,组内统计后,排序,进行组建统计
设A[1..n]是包含n个不同数的数组,如果i而且A[i]>A[j],则(i,j)为一个逆序组,给出时间复杂度为nlgn算法,确定n个任意元素排列中逆序组的个数。
> #include using namespace std; const int MAX=50005; int a[MAX],tree[MAX],n; int lowbit(int x) //找最低位的1 { return x&-x; } void add(int i,int x)//修改数据在i加x { while(i0) ...树
求逆序数的方法很多。最容易想到的办法是分别对序列中每一个元素求其逆序数,再求所有元素的逆序数总和,易分析得出这样的方法其时间复杂度为O(n2)。而这里采用的分治法求逆序数,其时间复杂度为O(nlogn)。
算法-数组逆序重存放(信息学奥赛一本通-T1105).rar
java基础面试题数组中逆序对本资源系百度网盘分享地址
有一实数序列a1,a2,....an,若i且ai>aj,则(ai,aj)形成了一个逆序对,请使用分治算法求整个序列中逆序对个数,并分析算法时间复杂度。
给你m个整数,将其逆序输出 输入 第一行一个整数m(3 ):数的个数 第二行m个整数(空格隔开)(这些数在0-9999999之间) 输出 m个整数(空格隔开
将数组中的数逆序排放
将数组中的数逆序排放
既然我们之前已经学了不少倒序的方法了,今天我们就进入实战,看看在数组中的逆序是如何输出的吧。 将一个数组逆序输出,用第一个与最后一个交换。 #!/usr/bin/python # -*- coding: UTF-8 -*- if __name__ == '__...
数组逆序数排列c语言
此程序是课程学习中的数组逆序,希望对大家有帮助
C语言——借助指针实现数组元素的逆序.zip
归并排序求逆序数
C语言的数组逆序,很实用的,可以下载试试,哈哈哈哈哈哈哈
算法导论 课上的 用mergesort求逆序数对的matlab源码,想挣点分,所以就不免费下载了~~~~ 见谅
输入一个数组,求出这个数组中的逆序对的总数。 示例 1: 输入: [7,5,6,4] 输出: 5 限制: 0 <= 数组长度 <= 50000 首先最容易想到的是暴力解法。 方法一:暴力解法(超时) 使用两层 for 循环枚举所有的数对,...