???这代码怎了0pt

P1908 逆序对

FlowerAccepted @ 2025-01-11 11:33:09

rt.WA?TLE?????蒟蒻求条QWQ
记录
code:

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int a[500005], t[500005];
long long ans;

void merge_sort(int a[], int l, int r) {
    if (l == r) {
        return;
    }
    int mid = (l + r) >> 1;
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);
    for (int i = 1, j = 1, k = mid + 1; i <= r; i ++) {
        if (j == mid + 1) {
            t[i] = a[k ++];
        } else if (k == r + 1) {
            t[i] = a[j ++];
            ans += k - mid - 1;
        } else if (a[j] <= a[k]) {
            t[i] = a[j ++];
            ans += k - mid - 1;
        } else {
            t[i] = a[k ++];
        }
    }
    for (int i = l; i <= r; i ++) {
        a[i] = t[i];
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
    }
    merge_sort(a, 1, n);
    cout << ans;
    return 0;
}

by FlowerAccepted @ 2025-01-11 11:36:20

原来是两个误入的1充当了l。
问题解决。
管理看到就把帖子锁了罢。

by be_the_person @ 2025-01-11 11:53:26

@FlowerAccepted 网上查的


#include<bits/stdc++.h>
#define M 500005
using namespace std;
int a[M],t[M],n;
long long ans=0;
void msort(int l,int r)
{
    if(l==r) return ;

    int mid=l+r>>1;
    msort(l,mid);   msort(mid+1,r);

    int i=l, j=mid+1, k=l;
    while(i<=mid&&j<=r)
        if(a[i]<=a[j]) t[k++]=a[i++];
        else t[k++]=a[j++], ans+=mid-i+1;

    while(i<=mid) t[k++]=a[i++];
    while(j<=r)   t[k++]=a[j++];

    for(int i=l;i<=r;i++) a[i]=t[i];
}
int main()
{
//  freopen("in.txt","r",stdin);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    msort(1,n); 
    cout<<ans;
    return 0;
}