P1908归并模板

幻蓝刀心 · 2019-07-30 11:29:47 · 个人记录

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=600000;
int n;
long long ans=0;
int a[maxn],b[maxn];
int get()
{
    char ch;int x=0;int p=1;
    ch=getchar();
    while(ch<'0' || ch>'9')
        ch=getchar();
    if(ch=='-')p=-1;
    while(ch>='0' && ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^'0');
        ch=getchar();
    }
    return p*x;
}
void  msort(int l,int r)
{
      if(l<r)
      {
        int mid=(l+r)>>1;
        msort(l,mid),msort(mid+1,r);
        for(int i=l;i<=mid;i++)
          b[i]=a[i];
        for(int i=r,j=mid+1;j<=r;i--,j++)
          b[i]=a[j];
        for(int k=l,i=l,j=r;k<=r;k++)
          if(b[i]<=b[j])
            a[k]=b[i++];
          else
            a[k]=b[j--],ans+=mid-i+1;
      }
}
int main()
{
    n=get();
    for(int i=1;i<=n;i++)
       a[i]=get();
    msort(1,n);
   /* for(int i=1;i<n;i++)
      printf("%d ",a[i]);
    printf("%d\n",a[n]);*/
    printf("%lld\n",ans);
    //system("pause");
    return 0;
}