并归排序看得我一愣一愣的.....大概我真的不适合队列 排序啥的 我是个废人 瘟得伤心
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; #define ll long long #define rg register #define Max(x,y) (x)>(y)?(x):(y) #define Min(x,y) (x)>(y)?(y):(x) const int N=500000+5,M=200000+5,inf=0x3f3f3f3f,P=19650827; int n,a[N],rk[N]; ll ans=0ll; template <class t>void rd(t &x){ x=0;int w=0;char ch=0; while(!isdigit(ch)) w|=ch==‘-‘,ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=w?-x:x; } void mergesort(int l,int r){ if(l>=r) return; int mid=(l+r)>>1,pl=l,pr=mid+1,k=l; mergesort(l,mid),mergesort(mid+1,r); while(pl<=mid&&pr<=r) if(a[pl]<=a[pr]) rk[k++]=a[pl++]; else rk[k++]=a[pr++],ans+=(ll)mid-pl+1; while(pl<=mid) rk[k]=a[pl],++k,++pl; while(pr<=r) rk[k]=a[pr],++k,++pr; for(int i=l;i<=r;++i) a[i]=rk[i]; } int main(){ // freopen("in.txt","r",stdin); rd(n); for(int i=1;i<=n;++i) rd(a[i]); mergesort(1,n); printf("%lld",ans); return 0; }
原文:https://www.cnblogs.com/lxyyyy/p/11178011.html