xeri_chen @ 2019-06-28 17:28:39
可能我的归并不够标准但应该是对的吧。
#include<bits/stdc++.h>
using namespace std;
const int N=100000;
int a[6*N];
long long ans;
void px(int bin,int end)
{
if(end-bin<=1) return;
int mid=(bin+end)/2;
px(bin,mid);
px(mid,end);
int s[N]={},n=end-bin,na=bin,nb=mid;
for(int i=0;i<n;i++)
{
if(a[na]>a[nb])
{
s[i]=a[nb++];
ans+=mid-na;
}
else
{
s[i]=a[na++];
}
if(na==mid)
{
while(nb!=end)
{
s[++i]=a[nb++];
}
break;
}
if(nb==end)
{
while(na!=mid)
{
s[++i]=a[na++];
}
break;
}
}
na=0;
for(int i=bin;i<end;i++)
a[i]=s[na++];
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
px(0,n);
cout<<ans;
return 0;
}
by Jelly_Goat @ 2019-06-28 17:58:04
@xeri_chen
把辅助数组开到全局就OK了
好像是分配空间的事
这个好像也需要time
我一开始也是TLE
by aminoas @ 2019-06-28 18:04:53
树状数组大法好
by _Sein @ 2019-06-28 18:55:41
@xeri_chen 初始化数组需要时间,相当于memset
by xeri_chen @ 2019-06-28 21:51:44
原来如此,本蒟蒻受教了,谢谢各位大佬