daijinxiang @ 2024-08-25 11:38:22

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=5e5+5;
int n,ans;
int a[N],r[N];
void gsort(int s,int t) {
    if(s>=t) return;
    int mid=(s+t)/2;
    gsort(1,mid);
    gsort(mid+1,t);
    int i=s,j=mid+1,k=s;
    while(i<=mid&&j<=t) {
        if(a[i]<=a[j]) r[k++]=a[i++];
        else {
            r[k++]=a[j++];
            ans+=mid-i+1;
        }
    }
    while(i<=mid) r[k++]=a[i++];
    while(j<=t) r[k++]=a[j++];
    for(int i=s; i<=t; i++)
        a[i]=r[i];
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    gsort(1,n);
    cout<<ans<<endl;
    return 0;
}

by wujunxi206 @ 2024-08-25 11:40:42

#include<iostream>
using namespace std;
int n;
long long ans=0;
int a[100005],b[100005];
void mere_sort(int l,int r){
    if(l==r) return ;
    int mid=(l+r)>>1;
    mere_sort(l,mid);
    mere_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];
            i++,k++;
        }else{
            ans+=mid-i+1;
            b[k]=a[j];
            j++,k++;
        }
    }
    while(i<=mid){
        b[k]=a[i];
        i++,k++;
    }
    while(j<=r){
        b[k]=a[j];
        j++,k++;
    }
    for(int i=l;i<=r;i++){
        a[i]=b[i];
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    mere_sort(1,n);
    cout<<ans<<endl;
    return 0;
}

by wujunxi206 @ 2024-08-25 11:41:54

@daijinxiang 函数忘记加return ；

by daijinxiang @ 2024-08-25 11:42:39

@wujunxi206 所以你的代码和我有什么区别？？？

by daijinxiang @ 2024-08-25 11:43:45

@wujunxi206 加了

if(s==t) return;

by wujunxi206 @ 2024-08-25 11:47:35

https://www.luogu.com.cn/record/174626109

by daijinxiang @ 2024-08-25 11:48:01

@wujunxi206 我知道了。

gsort(1,mid);

应该改成

gsort(s,mid);

by wujunxi206 @ 2024-08-25 11:49:44

@daijinxiang 求关注

by daijinxiang @ 2024-08-25 11:51:15

@wujunxi206 额，这是我自己改的，你说的不对啊，咋给关注？

• 轻轻吐槽

by wujunxi206 @ 2024-08-25 11:51:51

我只是求

by abcaawtq @ 2024-08-25 11:58:42

@daijinxiang 不是 我刚改出来刚要发

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const long long N=5e5+5;
long long n,ans;
long long a[N],r[N];
void gsort(long long s,long long t) {
    if(s==t) return;
    long long mid=(s+t)/2;
    gsort(s,mid);
    gsort(mid+1,t);
    long long i=s,j=mid+1,k=s;
    while(i<=mid&&j<=t) {
        if(a[i]<=a[j]) r[k++]=a[i++];
        else {
            r[k++]=a[j++];
            ans+=mid-i+1;
        }
    }
    while(i<=mid) r[k++]=a[i++];
    while(j<=t) r[k++]=a[j++];
    for(long long i=s; i<=t; i++)
        a[i]=r[i];
}
int main() {
    cin>>n;
    for(long long i=1; i<=n; i++) cin>>a[i];
    gsort(1,n);
    cout<<ans<<endl;
    return 0;
}