#2019120500016 逆序对与归并排序

P1908 归并排序与逆序对

1

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#define N 1000005
int c[N],a[N];
int n;
long long ans=0;
void merge_sort(int l,int r){
    if(l==r) return ;
    int mid=(l+r)/2;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    int q1=l,q2=mid+1;
    for(int qY=l;qY<r;qY++){
        if(q1>mid) c[qY]=a[q2],q2++;
        else if(q2>r) c[qY]=a[q1],q1++;
        else if(a[q1]<=a[q2]) c[qY]=a[q1],q1++;
        else c[qY]=a[q2],q2++,ans+=(mid-q1+1);//逆序对用ans 
    }
    
    //while(q1<=mid&&q2>=r){
    //  if(a[q1]<=a[q2]) c[qY]=a[q1],qY++,q1++;
    //  else c[qY]=a[q2],qY++,q2++,ans+=(mid-q1+1);
    //}
    //while (q1<=mid) c[qY]=a[q1],qY++,q1++;
    //while(q2<=r) c[qY]=a[q2],qL++,q2++;
    for(int i=l;i<=r;i++) a[i]=c[i];
} 
int main( ){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    merge_sort(1,n);
    printf("%lld",ans);
    return 0;
}

2

LGTJ

#include<cstdio>
#define msort merge_sort
#define ll long long
using namespace std;
const int maxn=5e5+5;
int a[maxn],r[maxn],n;
long long ans=0; 
void msort(int s,int t){
    if(s==t) return ;
    int mid=(s+t)/2;
    msort(s,mid);
    msort(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],k++,i++;//先赋值再+1 
        else r[k]=a[j],k++,j++,ans+=(ll)mid-i+1;//理解为数学归纳
    while(i<=mid) r[k]=a[i],k++,i++;
    while(j<=t) r[k]=a[j],k++,j++;
    for(int i=s;i<=t;i++) a[i]=r[i];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    msort(1,n);
    printf("%lld\n",ans);
    return 0;
}

#2019120500016 逆序对与归并排序

原文：https://www.cnblogs.com/liuziwen0224/p/11992435.html