Kater_kcl @ 2019-07-25 23:39:24
#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <set>
#include <vector>
#include <algorithm>
#include <cstdio>
#define ll long long
#define maxn 500005
using namespace std;
ll m[maxn];
int ans=0;
void mysort(ll l,ll r,ll mm[]){//左闭右开
if (r-l<=1) {
mm[0]=m[l];
return;
}
ll mid=(l+r)/2;
ll lt[mid-l+1],rt[r-mid+1];
mysort(l, mid, lt);
mysort(mid, r, rt);
int pointl=0,pointr=0,i=0;
while(pointl!=mid-l&&pointr!=r-mid){
if(lt[pointl]<rt[pointr])
mm[i++]=lt[pointl++];
else{
mm[i++]=rt[pointr++]; ans+=mid-pointl;}
}
if(pointl!=mid-l)
while (i!=r-l) {mm[i++]=lt[pointl++];}
else
while (i!=r-l) {mm[i++]=rt[pointr++];}
}
int main(){
int n;
cin>>n;
for (int i=0; i<n; i++) {
scanf("%lld", &m[i]);
}
mysort(0, n, m);
cout<<ans;
return 0;
}
by 万弘 @ 2019-07-26 07:52:49
@Kater_kcl ll lt[mid-l+1],rt[r-mid+1];
是什么操作
by Kater_kcl @ 2019-07-26 09:12:28
@万弘 左右辅助数组啊(萌新不会只定义一个数组)
by 万弘 @ 2019-07-26 09:36:32
@Kater_kcl 你是RE还是WA
by Kater_kcl @ 2019-07-26 09:36:51
@万弘 wa
by 万弘 @ 2019-07-26 09:39:54
mysort(l, mid, lt);
mysort(mid, r, rt);
应该改成
mysort(l, mid, lt);
mysort(mid+1, r, rt);
by Kater_kcl @ 2019-07-28 13:32:11
@万弘 谢谢谢谢
by Kater_kcl @ 2019-07-28 13:35:31
@万弘 但是改了之后依然不对啊QAQ