代码

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC optimize("3")
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
using namespace std;
typedef pair<int,int> PII;
const int N=1e5+5;
uint c[65536],b[N];
inline void sort(uint *a,int n){
    if(n<=1e5){
        memset(c,0,sizeof(c));
        for(int i=0;i<n;++i)++c[a[i]&65535];
        for(int i=1;i<65536;++i)c[i]+=c[i-1];
        for(int i=n-1;~i;--i)b[--c[a[i]&65535]]=a[i];
        memset(c,0,sizeof(c));
        for(int i=0;i<n;++i)++c[b[i]>>16];
        for(int i=1;i<65536;++i)c[i]+=c[i-1];
        for(int i=n-1;~i;--i)a[--c[b[i]>>16]]=b[i];
    }
    else{
        sort(a,n/2),sort(a+n/2,n-n/2);
        inplace_merge(a,a+n/2,a+n);
    }
}

评测结果