样例已过，但全WA

P1908 逆序对

3_14 @ 2024-07-17 10:14:11

Code：

#include<bits/stdc++.h>
#define str to_string
using namespace std;
using ll=long long;
const int MAX=5e5+1;
int a[MAX],b[MAX],cnt=0;
void merge_sort(int l,int r){
    cnt++;
    if(l==r)return;
    int mid=l+r>>1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r)
        if(a[i]<a[j])b[k++]=a[i++];
        else b[k++]=a[j++];
    while(i<=mid)b[k++]=a[i++];
    while(j<=r)b[k++]=a[j++];
    for(int i=l;i<=r;i++)a[i]=b[i];
}
int n;
int main(){
    cin>>n; 
    for(int i=1;i<=n;i++)cin>>a[i];
    merge_sort(1,n);
    cout<<cnt<<'\n';
    return 0;
}

by Melo_DDD @ 2024-07-17 10:18:21

@3_14 你的 cnt 为什么要放在那里啊，建议思考一下逆序对的原理

by 3_14 @ 2024-07-17 10:19:15

@shin_chan_jiang cnt 该放哪里？

by Melo_DDD @ 2024-07-17 10:22:16

@3_14

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

by caoshuchen @ 2024-07-17 10:31:45

你应该进行双指针，查找左边大于右边的个数，这里需要增加 $cnt$。为什么呢？因为此时左右两边已经搜过了，是排好序的，但是可以保证的是左边的所有数的原来的序号依然一定小于右边的所有数。因此，我们只需要找到对于每个左边的元素编号 $i$，有多少个右边元素编号 $j$ 使得 $a_i>a_j$ 即可。由于 $a_i$ 已经递增排序，所以 $j$ 也是随 $i$ 的增加而增加，不会减小。所以使用双指针即可。我的代码（注意，我是左闭右开的写法）： ```c++ #include <iostream> using namespace std; int n; long long a[500005], t[500005]; long long slv(int l, int r) { if (l + 1 == r) return 0; int m = (l + r) / 2; long long cnt = slv(l, m) + slv(m, r); for (int i = l - 1, j = m; j < r; j++) { while (i + 1 < m && a[i + 1] > a[j]) i++; cnt += i - l + 1; } for (int i = l, cur = l, j = m; i < m || j < r; ) { if (i < m && (j == r || a[i] > a[j])) t[cur++] = a[i++]; else t[cur++] = a[j++]; } for (int i = l; i < r; i++) a[i] = t[i]; return cnt; } int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; cout << slv(1, n + 1); return 0; } ```

by caoshuchen @ 2024-07-17 10:32:49

@3_14 我赌你的 cnt 一定输出的结果是 n\log_2n 左右

by 3_14 @ 2024-07-17 10:37:53

@caoshuchen 主要是才学完归并

by caoshuchen @ 2024-07-17 10:40:23

@3_14 问题不大，当初我也差不多。我现在就正在学点分治。