逆数

求解逆序数问题

当某两个元素的先后次序与标准次序（从⼩到⼤的顺序）不同时，就说有1个逆序。⼀个排列中所有逆序总数叫做这个排列的逆序数。

⽅法⼀：利⽤归并排序求解

归并排序的主要思想是将整个序列分成两部分，分别递归将这两部分排好序之后，再和并为⼀个有序的序列。

在合并的过程中是将两个相邻并且有序的序列合并成⼀个有序序列，如以下两个有序序列

Seq1：345

Seq2：26田园日记7 89

合并成⼀个有序序:

Seq：2345689

对于序列q1中的某个数a[i],序列q2中的某个数a[j]，如果a[i]a[j]，那么逆序数为q1中a[i]后边元素的个

数(包括a[i])，即len1-i+1,

这样累加每次递归过程的逆序数，在完成整个递归过程之后，最后的累加和就是逆序的总数

求逆序数

时间限制：2000ms|内存限制：65535KB

难度：5

描述

在⼀个排列中，如果⼀对数的前后位置与⼤⼩顺序相反，即前⾯的数⼤于后⾯的数，那么它们就称为⼀个逆序。⼀个排列中逆序的总数就称

为这个排列的逆序数。

现在，给你⼀个N个元素的序列，请你判断出它的逆序数是多少。

⽐如132的逆序数就是1。

输⼊第⼀⾏输⼊⼀个整数T表⽰测试数据的组数（1<=T<=5)

每组测试数据的每⼀⾏是⼀个整数N表⽰数列中共有N个元素（2〈=N〈=1000000）

随后的⼀⾏共有N个整数Ai(0<=Ai<1000000000)，表⽰数列中的所有元素。

数据保证在多组测试数据中，多于10万个数的测试数据最多只有⼀组。

输出输出该数列的逆谚语的英文 序数

样例输⼊

2

2

11

3

132

样例输出

0

1

#include

#include

#include

#include

#include

#include

#include

#definelllonglong

#defineDBdouble

#defineinf2

#definemod1000000007

usingnamespacestd;

constintN=1e5+90;

intn,a[N*60],b[N*60];

llans;//ans为逆序对个数

voidmerge_sort(intl,intr)

{

if(l==r)return;

intmid=(l+r)/2,i,j,k;

i=l;k=l;j=mid+1;

merge_小学英语说课稿 sort(l,mid);

merge_sort(mid+1,r);

while(i<=mid&&j<=r)

{

if(a并驾齐驱 [i]<=a[j])b[k++]=a[i++];

elans+=mid-i+1,b[k++]=a[j++];

}

while(i<=mid)b[k++]=a[i++];

while(j<=r)b[k++]=a[j++];

for(into=l;o<=r;++o)a[o]=b[o];

}

intmain()

{

scanf("%d",&n);

for(inti=1;i<=n;++i)scanf("%d",&a[i]);

merge_sort(1,n);

for(inti=1;i<=n;++i)printf("%d",a[i]);

//printf("%lld",ans);

return0;

}

#include

#definemax100立春日感怀 0001

longlonga[max],b[max];

longlongcount;

voidMerge(longlonga[],intstart,intmid,intend)//归并排序的合并部分

{

inti=start,j=mid+1,k=start;

while(i<=mid&&j<=end)

{

if(a[i]<=a[j])

{

b[k++]=a[i++];

}

el

{

count+=j-k;//统计逆序数对

b[k++]=a[j++];

}

}

while(i<=mid)

{

b[k++]=a[i++];

}

while(j<=end)

{

b[k++]=a[j++搞笑桌面壁纸 ];

}

for(inti=start;i<=end;i++)

{

a[i]=b[i];

}

}

voidMergeSort(longlonga[],intstart,intend)//归并排序

{

if(start

{

intmid=(start+end)/2;

MergeSort(a,start,mid);//将前半部分排序

MergeSort(a,mid+1,end);//将后半部分排序

Merge(a,start,mid,end);//合并前后两个部分

}

}

}

intmain(intargc,charconst*argv[])

{

intn,m;

scanf("%d",&n);

while(n--)

{

scanf("%d",&m);

count=0;

for(inti=0;i

{

scanf("%d",a+i);

}

MergeSort(a,0,m-1);

printf("%lldn",count);

}

return0;

}

⽅法⼆：树状数组求解

树状数组实际上还是⼀个数组，只不过它的每个元素保存了跟原来数组的⼀些元素相关的结合值。

若A为原数组，定义数组C为树状数组。C数组中元素C[i]表⽰A[i–lowbit(i)+1]⾄A[i]的结合值。

lowbit(i)是i的⼆进制中最后⼀个不为零的位数的2次⽅，可以这样计算

lowbit(i)=x&(-x)

lowbit(i)=x&(x^(x-1))

当想要查询⼀个sum(n)时，可以依据如下算法即可：

step1:令sum=0，转第⼆步；

step2:假如n<=0，算法结束，返回sum值，否则sum=sum+Cn，转第三步；

step3:令n=n–lowbit(n)，转第⼆步。

n=n–lowb个人感言 it(n)这⼀步实际上等价于将n的⼆进制的最埃及港口 后⼀个1减去。⽽n的⼆进制⾥最多有log(n)个1，所以查询效率是log(n)的。

修改⼀个节点，必须修改其所有祖先，最坏情况下为修改第⼀个元素，最多有log(n)的祖先。所以修改算法如下（给某个结点i加上x）：

step1:当i>n时，算法结束，否则转第⼆步；

step2:Ci=Ci+x，i=i+lowbit(i)转第⼀步。

i=i+lowbit(i)这个过程实际上也只是⼀个把末尾1补为0的过程。

求逆序的思路：

可以把数⼀个个插⼊到树状数组中，每插⼊⼀个数，统计⽐他⼩的数的个数，对应的逆序为i-getsum(data[i])，其中i为当前已经插⼊

的孤独一人 数的个数，getsum(data[i]）为⽐data[i]⼩的数的个数，i-getsum(data[i])即⽐data[i]⼤的个数，即逆序的个数。最后需要把

所有逆序数求和，就是在插⼊的过程中边插⼊边求和。

#include

#include

#include

#include

#include

#include

usingnamespacestd;

constintmaxn=500005;

intn;

intaa[maxn];//离散化后的数组

intc[maxn];//树状数组

structNode{

intv;

intorder;

}in[maxn];

intlowbit(intx)

{

returnx&(-x);

}

voidupdate(intt,intvalue)

{

inti;

for(i=t;i<=n;i+=lowbit(i))

{

c[i]+=value;

}

}

intgetsum(intx)

{

inti;

inttemp=0;

for(i=x;i>=1;i-=lowbit(i))

{

temp+=c[i];

}

returntemp;

}

boolcmp(Nodea,Nodeb)

{

returna.v

}

intmain()

{

inti,j;

while(scanf("%d",&n)==1&&n)

{

//离散化

for(i=1;i<=n;i++)

{

scanf("%d",&in[i].v);

in[i].order=i;

}

sort(in+1,in+n+1,cmp);

for(i=1;i<=n;i++)aa[in[i].order]=i;

//树状数组求逆序

memt(c,0,sizeof(c));

longlongans=0;

for(i=1;i<=n;i++)

{

update(aa[i],1);

update(aa[i],1);

ans+=i-getsum(aa[i]);

}

cout<

}

return0;

}