用两种求法求的逆序数_百度知道
用两种求法求的逆序数
提问者采纳
比1大顺：还有一种从后往前，比7大的有一个8，看你喜欢怎么用就选哪一种，6两个，这是第二种，嗯，再6：先看前面的1，8比8大的没有1，以后其他依次，7，接着4比4大的有5，以后依次，有几个小就加几这是一种，在3比6小逆，然后是顺的。2
提问者评价
其他类似问题
逆序数的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁线段树或树状数组求逆序数 - 推酷
线段树或树状数组求逆序数
线段树或树状数组求逆序数
&&&&&&&& 求逆序数的方法有分治，归并，本文只介绍线段树或树状数组求逆序数的办法，众所周知，线段树和树状树可以用来解决区间操作问题，就是因为这两个算法区间操作的时间复杂度很低O(logN)，才让这种方法具有可行性。
&&&&&&&& 首先先来看一个序列&& 6 1 2 7 3 4 8 5，此序列的逆序数为5+3+1=9。冒泡法可以直接枚举出逆序数，但是时间复杂度太高O(n^2)。冒泡排序的原理是枚举每一个数组，然后找出这个数后面有多少个数是小于这个数的，小于它逆序数+1。仔细想一下，如果我们不用枚举这个数后面的所有数，而是直接得到小于这个数的个数，那么效率将会大大提高。&&&&&&&&&&
&&&&&&&& 总共有N个数，如何判断第i+1个数到最后一个数之间有多少个数小于第i个数呢？不妨假设有一个区间 [1,N]，只需要判断区间[i+1,N]之间有多少个数小于第i个数。如果我们把总区间初始化为0，然后把第i个数之前出现过的数都在相应的区间把它的值定为1，那么问题就转换成了[i+1,N]值的总和。再仔细想一下，区间[1,i]的值+区间[i+1,N]的值=区间[1,N]的值(i已经标记为1)，所以区间[i+1,N]值的总和等于N-[1,i]的值！因为总共有N个数，不是比它小就是比它(大或等于)。
&&&&&&&&现在问题已经转化成了区间问题，枚举每个数，然后查询这个数前面的区间值的总和，
既为逆序数。
&&&&&&& 线段树预处理时间复杂度O(NlogN)，N次查询和N次插入的时间复杂度都为O(NlogN)，总的时间复杂度O(3*NlogN)
&&&&&&& 树状数组不用预处理，N次查询和N次插入的时间复杂度都为O(NlogN)，总的时间复杂度O(2*NlogN)
#include &stdio.h&
#include &string.h&
#include &stdlib.h&
#define MAX 51000
#define MID(a,b) (a+b)&&1
#define R(a) (a&&1|1)
#define L(a) a&&1
typedef struct {
int num,left,
int ans[MAX];
Node Tree[MAX&&2];
void Build(int t,int l,int r)
//以1为根节点建立线段树
Tree[t].left=l,Tree[t].right=r;
if(Tree[t].left==Tree[t].right)
Tree[t].num=0;
mid=MID(Tree[t].left,Tree[t].right);
Build(L(t),l,mid);
Build(R(t),mid+1,r);
void Insert(int t,int l,int r,int x)
//向以1为根节点的区间[l,r]插入数字1
if(Tree[t].left==l&&Tree[t].right==r)
Tree[t].num+=x;
mid=MID(Tree[t].left,Tree[t].right);
Insert(R(t),l,r,x);
else if(r&=mid)
Insert(L(t),l,r,x);
Insert(L(t),l,mid,x);
Insert(R(t),mid+1,r,x);
Tree[t].num=Tree[L(t)].num+Tree[R(t)].
int Query(int t,int l,int r)
//查询以1为根节点，区间[l,r]的和
if(Tree[t].left==l&&Tree[t].right==r)
return Tree[t].
mid=MID(Tree[t].left,Tree[t].right);
return Query(R(t),l,r);
else if(r&=mid)
return Query(L(t),l,r);
return Query(L(t),l,mid)+Query(R(t),mid+1,r);
int main()
int a,n,i,t;
scanf(&%d&,&t);
while(t--)
scanf(&%d&,&n);
memset(Tree,0,sizeof(Tree));
//初始化线段树
Build(1,1,n);
for(i=1;i&=n;i++)
//输入n个数
scanf(&%d&,&ans[i]);
for(i=1,k=0;i&=n;i++)
Insert(1,a,a,1);
//把线段树[ans[i],ans[i]]区间的值插入为1
k=k+(i-Query(1,1,a));
//查询区间[1,ans[i]]值的总和,逆序数等于i-[1,ans[i]]
printf(&%lld\n&,k);
// 树状数组
#include &stdio.h&
#include &stdlib.h&
#include &string.h&
#include &algorithm&
#define MAX 100010
int c[MAX],a[MAX],ans[MAX],n;
int Lowbit(int x)
//返回二进制最后一个1所表示的数
return x&(-x);
void Updata(int x)
//向前更新
while(x&=n)
x+=Lowbit(x);
int Sum(int x)
//向后更新求和
int sum=0;
while(x&0)
sum+=c[x];
x-=Lowbit(x);
int main()
int i,t,k;
scanf(&%d&,&t);
while(t--)
scanf(&%d&,&n);
for(i=1;i&=n;i++)
scanf(&%d&,&ans[i]);
memset(c,0,sizeof(c));
//初始化树状数组
for(i=1,k=0;i&=n;i++)
Updata(ans[i]);
//向后更新节点ans[i].k
k=k+(i-Sum(ans[i]));
//向前查询节点ans[i].k
printf(&%d\n&,k);
已发表评论数()
&&登&&&陆&&
已收藏到推刊！
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
树状数组求逆序数原理
下载积分：600
内容提示：
文档格式：DOC|
浏览次数：11|
上传日期： 07:33:00|
文档星级：
该用户还上传了这些文档
树状数组求逆序数原理.DOC
官方公共微信给定n,k，如何求出1~n排列中所有逆序数为k者？
[问题点数：20分，结帖人iwantnon]
给定n,k，如何求出1~n排列中所有逆序数为k者？
[问题点数：20分，结帖人iwantnon]
不显示删除回复
显示所有回复
显示星级回复
显示得分回复
只显示楼主
2010年3月 专题开发/技术/项目大版内专家分月排行榜第二2009年6月 专题开发/技术/项目大版内专家分月排行榜第二2009年5月 专题开发/技术/项目大版内专家分月排行榜第二2009年1月 专题开发/技术/项目大版内专家分月排行榜第二
2010年11月 专题开发/技术/项目大版内专家分月排行榜第三2010年5月 专题开发/技术/项目大版内专家分月排行榜第三2009年12月 专题开发/技术/项目大版内专家分月排行榜第三2009年11月 专题开发/技术/项目大版内专家分月排行榜第三2009年8月 专题开发/技术/项目大版内专家分月排行榜第三2009年4月 专题开发/技术/项目大版内专家分月排行榜第三2009年3月 专题开发/技术/项目大版内专家分月排行榜第三2008年12月 专题开发/技术/项目大版内专家分月排行榜第三
2010年3月 专题开发/技术/项目大版内专家分月排行榜第二2009年6月 专题开发/技术/项目大版内专家分月排行榜第二2009年5月 专题开发/技术/项目大版内专家分月排行榜第二2009年1月 专题开发/技术/项目大版内专家分月排行榜第二
2010年11月 专题开发/技术/项目大版内专家分月排行榜第三2010年5月 专题开发/技术/项目大版内专家分月排行榜第三2009年12月 专题开发/技术/项目大版内专家分月排行榜第三2009年11月 专题开发/技术/项目大版内专家分月排行榜第三2009年8月 专题开发/技术/项目大版内专家分月排行榜第三2009年4月 专题开发/技术/项目大版内专家分月排行榜第三2009年3月 专题开发/技术/项目大版内专家分月排行榜第三2008年12月 专题开发/技术/项目大版内专家分月排行榜第三
2007年10月 专题开发/技术/项目大版内专家分月排行榜第二
2010年3月 专题开发/技术/项目大版内专家分月排行榜第二2009年6月 专题开发/技术/项目大版内专家分月排行榜第二2009年5月 专题开发/技术/项目大版内专家分月排行榜第二2009年1月 专题开发/技术/项目大版内专家分月排行榜第二
2010年11月 专题开发/技术/项目大版内专家分月排行榜第三2010年5月 专题开发/技术/项目大版内专家分月排行榜第三2009年12月 专题开发/技术/项目大版内专家分月排行榜第三2009年11月 专题开发/技术/项目大版内专家分月排行榜第三2009年8月 专题开发/技术/项目大版内专家分月排行榜第三2009年4月 专题开发/技术/项目大版内专家分月排行榜第三2009年3月 专题开发/技术/项目大版内专家分月排行榜第三2008年12月 专题开发/技术/项目大版内专家分月排行榜第三
2010年3月 专题开发/技术/项目大版内专家分月排行榜第二2009年6月 专题开发/技术/项目大版内专家分月排行榜第二2009年5月 专题开发/技术/项目大版内专家分月排行榜第二2009年1月 专题开发/技术/项目大版内专家分月排行榜第二
2010年11月 专题开发/技术/项目大版内专家分月排行榜第三2010年5月 专题开发/技术/项目大版内专家分月排行榜第三2009年12月 专题开发/技术/项目大版内专家分月排行榜第三2009年11月 专题开发/技术/项目大版内专家分月排行榜第三2009年8月 专题开发/技术/项目大版内专家分月排行榜第三2009年4月 专题开发/技术/项目大版内专家分月排行榜第三2009年3月 专题开发/技术/项目大版内专家分月排行榜第三2008年12月 专题开发/技术/项目大版内专家分月排行榜第三
2010年3月 专题开发/技术/项目大版内专家分月排行榜第二2009年6月 专题开发/技术/项目大版内专家分月排行榜第二2009年5月 专题开发/技术/项目大版内专家分月排行榜第二2009年1月 专题开发/技术/项目大版内专家分月排行榜第二
2010年11月 专题开发/技术/项目大版内专家分月排行榜第三2010年5月 专题开发/技术/项目大版内专家分月排行榜第三2009年12月 专题开发/技术/项目大版内专家分月排行榜第三2009年11月 专题开发/技术/项目大版内专家分月排行榜第三2009年8月 专题开发/技术/项目大版内专家分月排行榜第三2009年4月 专题开发/技术/项目大版内专家分月排行榜第三2009年3月 专题开发/技术/项目大版内专家分月排行榜第三2008年12月 专题开发/技术/项目大版内专家分月排行榜第三
2010年3月 专题开发/技术/项目大版内专家分月排行榜第二2009年6月 专题开发/技术/项目大版内专家分月排行榜第二2009年5月 专题开发/技术/项目大版内专家分月排行榜第二2009年1月 专题开发/技术/项目大版内专家分月排行榜第二
2010年11月 专题开发/技术/项目大版内专家分月排行榜第三2010年5月 专题开发/技术/项目大版内专家分月排行榜第三2009年12月 专题开发/技术/项目大版内专家分月排行榜第三2009年11月 专题开发/技术/项目大版内专家分月排行榜第三2009年8月 专题开发/技术/项目大版内专家分月排行榜第三2009年4月 专题开发/技术/项目大版内专家分月排行榜第三2009年3月 专题开发/技术/项目大版内专家分月排行榜第三2008年12月 专题开发/技术/项目大版内专家分月排行榜第三
本帖子已过去太久远了，不再提供回复功能。请教一个线性代数问题,求逆序数的求(2k)1(2k-1)2(2k-2)3(2k-3)……(k+1)k 的逆序数?为什么答案是0+1+1+2+2+……+(k-1)+k_百度作业帮
请教一个线性代数问题,求逆序数的求(2k)1(2k-1)2(2k-2)3(2k-3)……(k+1)k 的逆序数?为什么答案是0+1+1+2+2+……+(k-1)+k
根据你的结果,其逆序数是这样计算的:对每个数,看其左边有几个比它大的数比如:0 2k 左边没有比它大的数1 1左边有1个比1大的数1 2k-1 左边有1个比2k-1大的数.PS.还有一种算法:对每个数,看其右边有几个比它小的数最后结果是一样的.
2k左边没有比它大的数为0，1左边有一个数比它大为1，2k-1左边有一个比它大为1，2左边有两个比它大为2，以此类推······所以答案就出来了
为什么这是“线性代数”问题？这和线性代数明明没有任何关系