合并的同时求逆序队数量，一语点醒梦中人

一直在纠结为什么算逆序对数量要排序，排序难道不会改变原数组的顺序吗？看到你这个题解，瞬间理解了。

只能说 好牛逼！

这逆向思维太牛逼了

#include<iostream>

using namespace std;

const int N = 1e5+10;

int a[N];
int main()
{
    int n ;
    cin>>n;
    for(int i = 0 ; i < n ; i ++) scanf("%d",&a[i]);
    int m;
    for(int i = 0; i < n -1; i++)
    for(int j = i +1; j < n; j ++)
    if(a[i]>a[j]) m++;
    cout<<m<<endl;
    return 0;
}

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~

这个为什么错QAQ啥也不会 感觉按脑子里最笨的想了一下就是这个

#include <iostream>

using namespace std;

const int N = 1e5+10;

int a[N];
int main()
{
    int n ;
    cin >> n;
    for (int i = 0 ; i < n ; i ++) scanf("%d",&a[i]);
    int m = 0;
    for (int i = 0; i < n ; i++)
        for(int j = i + 1; j < n ; j ++)
            if(a[i] > a[j]) m ++;
    cout << m << endl;
    return 0;
}

是这样吧，但会超时

超时

冒泡排序效率有点低

m没初始化

初始化了 但是不能用int 要用longlong

好家伙直接暴力

悟了悟了，谢谢大佬
@xuanxuanxuan

#include[HTML_REMOVED]
using namespace std;
typedef long long LL;
const int N=1e6+10;
int q[N],tmp[N];
int n;
LL res=0;
LL merge_sort(int q[],int l,int r)
{
if(l>=r)return 0;
int mid=l+r>>1;
//merge_sort(q,l,mid),merge_sort(q,mid+1,r);
LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
int i=l;
int j=mid+1;
int k=0;

while(i<=mid&&j<=r)
{
    if(q[i]<=q[j])
        tmp[k++]=q[i++];
    else
    {
        tmp[k++]=q[j++];
        res+=mid-i+1;
    }

}
while(i<=mid)
    tmp[k++]=q[i++];
while(j<=r)
    tmp[k++]=q[j++];
for(i=l,j=0;i<=r;i++,j++)
    q[i]=tmp[j];
return res;

}

int main()
{

scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d ",&q[i]);
res=merge_sort(q,0,n-1);
printf("%lld",res);
return 0;

}
在merge函数里添加“merge_sort(q,l,mid),merge_sort(q,mid+1,r); ”给的样例就输出不对，删去这一行就能AC

想问问大佬们：
为什么q[i]>q[j]的时候是res+=mid-i+1而不是res+=mid-i呢

为什么要加一个1呢

从i到mid一共mid-i+1个数，比如从1到5一共5-1+1=5个数

懂了懂了蟹蟹

根本看不懂。我怀疑我脑子有问题。

牛逼，终于懂了，感谢分享

大佬Orz

原来是这样

判断左右序列大小时，如果是逆序，则res+= mid-i+1;第一次归并生成逆序对1个，第二次归并生成逆序对3个，第三次归并逆序对生成10个
if(q[i]<=q[j]) tmp[k]=q[i];
else
{
tmp[k] = q[j];
res+= mid-i+1;
}

应该是第一次归并逆序对+1， 第二次归并逆序对+3，第三次归并逆序对+11。不太清楚3 + 4 + 4是怎么来的。

第三次是+10，所以最后是+1+3+10 = 14。

比较次数跟逆序对数又不是等价的。第一次归并比较了三次但是只有一次是逆序的。这题的思想就是在归并排序的比较中有多少逆序，求出来就行了。

确实，思想上是归并的时候检索有多少逆序，可能比较次数在第一次递归的时候比较好理解，因为底层递归的时候是有序单独的数字，在之后层数的话有循环的条件下，去考虑比较次数也许并不会对归并求逆序上的帮助不是特别大。

终于知道为什么可以直接使用mid-l+1来计算逆序数量了，，，因为每次归并所使用的上次归并的结果数组都是有序的，，所以如果是，[l,mid] 之间如果有q[i]大于右边数组q[j]的值，则[i,mid]之间的所有值都是大于q[j]的，，，可以用mid-l+1来计算

不是很清楚为什么逆序对是这样找出来的

看到你的评论才明白让数组排序的原因

终于理解了 感谢

一语点醒梦中人。

Orz

一语点醒梦中人

为什么比较次数就是逆序对的数量

没有呀，比较次数大于等于逆序数。只是在比较中求逆序数

麻烦能不能也帮我看一下为啥我的过不了呀？（开了longlong）
#include [HTML_REMOVED]
using namespace std;

const int N = 1000010;

int q[N], tmp[N];

long long count_inverse(int q[], int l, int r)
{
if (l >= r) return 0;
int mid = (l+r) >> 1;
long long res = count_inverse(q, l, mid) + count_inverse(q, mid+1, r);

int i = l, j = mid+1, k = 0;
while(i <= mid && j <= r)
{
    if(q[i]<=q[j]) tmp[k++] = q[i++];
    else 
    {
        res += mid - i + 1;
        tmp[k++] = q[j++]; 
    }
}

while(i <= mid) tmp[k++] = q[i++];
while(j <= r) tmp[k++] = q[j++];

for(int i = l, j=0; i<=r; i++, j++ ) q[i] = tmp[j];

return res;

}

int main()
{
int n;
scanf(“%d”, &n);

for(int i=0; i< n; i++) scanf("%d", &q[i]);

printf("%d", count_inverse(q, 0, n-1));

return 0;

}
感谢！！

tmp也开N个空间会超时吧，我java里会

而且long输出应该不是%d吧

tmp开N个空间不会超时；long long 输出%ld

兄弟，帮我看一下我哪错了吧 ，。，。

#include <iostream>
using namespace std;

const int N = 100005;

int a[N];

int count = 0;
void merge(int a[], int left, int right)
{
    int b[N] = {0};
    int mid = (left + right)/2;
    int l = left;
    int r = mid + 1;
    int index = 0;
    while(l <= mid && r <= right)
    {
        if(a[l] < a[r])
        {
            b[index++] = a[l++];
        }
        else 
        {
            count += mid - l +1;
            b[index++] = a[r++];

        }
    }
    while(l <= mid)
        b[index++] = a[l++];
    while(r <= right)
        b[index++] = a[r++];

    for(int i = left; i <= right; i++)
    {
        a[i] = b[i - left];
    }

}

void MergeSort(int a[], int left, int right)
{
    if(left >= right)
        return;
    int mid = (left + right)/2;
    MergeSort(a,left,mid);
    MergeSort(a,mid + 1, right);
    merge(a,left,right);
}
int main()
{
    int n = 0;
    scanf("%d",&n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    MergeSort(a,0,n-1);
    printf("%d\n", count);
}

while(l <= mid && r <= right)
{
if(a[l] <= a[r]) //这个地方少个=号，这个问题是解决了，但是你这种方法是课本上的排序方
//法，课本上的板子都缺少点优化，我刚才交了一下超时了，所以还是不行的，
//但是这种方法肯定是没问题的，就是没优化而已，你要是不打竞赛，平时考试
//啥的都没问题的，但是还是建议你看看y总的优化，挺不错的，大佬加油。
{
b[index] = a[l];
}
else
{
count += mid - l +1;
b[index] = a[r];

    }
}

我还没看呢，但是我看你们题解和我这种方法 一样啊，我感觉都是递归，为什么跑不过，能否指点一波

要开long long吧

开longlong啊 不开ll过不了

1.你这少开longlong,
2.a[l] <a[r]，少了等于 逆序对会求错
3 int b[N] = {0} ; 每个递归调用都o(n)赋初值，肯定TLE ；别赋值就行