归并排序：50pts+TLE

#include<bits/stdc++.h>
using namespace std;
//快读
const int BUFSIZE=1<<30;
char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
char getc(){
    if(is==it)
        it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
    return is==it?EOF:*is++;
}
int reads(){
    int ret=0;
    bool sign=0;
    char ch=getc();
    while(!isdigit(ch)){
        sign|=ch=='-';
        ch=getc();
    }
    while(isdigit(ch)){
        ret=ret*10+ch-'0';
        ch=getc();
    }
    return sign?-ret:ret;
}
//正片
int n,a[100005],b[100005],s; 
void merge(int l,int r){
    if(l==r) return;
    int mid=l+(r-l)/2;
    merge(l,mid);
    merge(mid+1,r);
    int i=l,j=mid+1,cnt=l-1;
    while(i<=mid && j<=r){
        if(a[i]>a[j]) s+=mid-i+1,b[++cnt]=a[j++];
        else b[++cnt]=a[i++];
    }
    while(i<=mid) b[++cnt]=a[i++];
    while(j<=r) b[++cnt]=a[j++];
    for(int k=l;k<=r;k++){
        a[k]=b[k];
    }
}
int main(){
    n=reads();
    for(int i=1;i<=n;i++){
        a[i]=reads();
    }
    merge(1,n);
    cout<<s;
}

评测记录