听取蛙声一片

P1908 逆序对

zhongyuZY @ 2023-10-15 11:35:38

#include<bits/stdc++.h>
using namespace std;
long long n,k;
int a[500005],b[500005];
long long f[16777216],ans;
void search_hh(int l,int r){
    int i,j,k;
    if(l>=r)return;
    int mid=(l+r)/2;
    search_hh(l,mid);
    search_hh(mid+1,r);
    for(int i=l;i<=r;i++)
    b[i]=a[i];
    i=l,j=mid+1;
    for(int k=l;k<=r;k++){
        if(i<=mid&&((j>r)||b[i]<b[j]))a[k]=b[i++];
        else{
        a[k]=b[j++];
        ans=ans+mid-i+1;    
        }
    }
}
int main(){
    int i,j,n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);  
    search_hh(0,n-1);
    printf("%lld",ans);
    return 0;
}
感谢大佬们!!!orz

by Disjoint_cat @ 2023-10-15 11:48:19

Hack:

2
1 1

应输出 0,你的程序输出 1

原因:b_i=b_j 时不应计入逆序对,所以

b[i]<b[j] \Rightarrow b[i]<=b[j] 即可。


by zhongyuZY @ 2023-10-15 11:59:55

@Donotplaygame woc大佬感谢万分!!!!膜拜


|