50求助

Main_Void_ @ 2023-07-27 17:48:26

#include <iostream>
using namespace std ;
const int N = 1e8;
typedef unsigned long long ULL ;
int q[N], tem[N], n ;

ULL merge_sort( int l, int r) {
    if ( l >= r)
        return 0 ;
    int mid = l + r >> 1 ;
    ULL res = merge_sort(l, mid) + merge_sort( mid + 1, r) ;
    int k = 0, i = l, j = mid + 1 ;
    while ( i <= mid && j <= r ) {
        if ( q[i] <= q[j])
            tem[k++] = q[i++] ;
        else {
            tem[k++] = q[j++] ;
            res += mid - i + 1 ;
        }
    }
    while ( i <= mid)
        tem[k++] = q[i++] ;
    while ( j <= r)
        tem[k++] = q[j++] ;
    for ( int i = l, j = 0 ; i <= r ; i++, j++) {
        q[i] = tem[j] ;
    }
    return res ;
}

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

by zyh_helen @ 2023-07-27 17:51:39

ULL输出错了

改成 cout 就行了

#include <iostream>
using namespace std ;
const int N = 1e8;
typedef unsigned long long ULL ;
int q[N], tem[N], n ;

ULL merge_sort( int l, int r) {
    if ( l >= r)
        return 0 ;
    int mid = l + r >> 1 ;
    ULL res = merge_sort(l, mid) + merge_sort( mid + 1, r) ;
    int k = 0, i = l, j = mid + 1 ;
    while ( i <= mid && j <= r ) {
        if ( q[i] <= q[j])
            tem[k++] = q[i++] ;
        else {
            tem[k++] = q[j++] ;
            res += mid - i + 1 ;
        }
    }
    while ( i <= mid)
        tem[k++] = q[i++] ;
    while ( j <= r)
        tem[k++] = q[j++] ;
    for ( int i = l, j = 0 ; i <= r ; i++, j++) {
        q[i] = tem[j] ;
    }
    return res ;
}

int main() {
    scanf("%d",&n);
    for ( int i = 0 ; i < n ; i ++)
        scanf("%d" , &q[i]) ;
    cout << merge_sort(0 , n - 1) ;
}

by Main_Void_ @ 2023-07-27 21:01:33

@zyh_helen 00 , 懂了 ， 谢谢大佬 ， 我还以为是我数组没开long long