GGAD @ 2019-10-05 19:06:42
#include<bits/stdc++.h>
using namespace std;
int n;
long long sum;
int a[500010];
int biu[500010];
void s(int x,int y) {
if(x==y) return;
int m=(x+y)/2;
s(x,m);
s(m+1,y);
int i=x,j=m+1,rua=x;
while(i<=m&&j<=y) {
if(a[i]<=a[j]) biu[rua++]=a[i++];
else biu[rua++]=a[j++],sum+=(long long)(m-i+1);
}
while(i<=m) biu[rua++]=a[i++];
while(j<=y) biu[rua++]=a[j++];
for(int k=1; k<=y; ++k) a[k]=biu[k];
}
int main() {
scanf("%d",&n);
for(int i=1; i<=n; ++i) scanf("%d",&a[i]);
s(1,n);
printf("%lld",sum);
return 0;
}by wmy_goes_to_thu @ 2019-10-05 19:09:20
我以前也是，不知道为什么，用树状数组过了
by wmy_goes_to_thu @ 2019-10-05 19:09:34
归并25分
by JT_kk @ 2019-10-05 19:14:34
@GGAD
for(int k=1; k<=y; ++k) a[k]=biu[k];
k=1 改成 k=x。
by GGAD @ 2019-10-05 20:34:34
@JT_kk 谢谢dalao，刚刚过了：D，因为之前在lemon上面测k=1过了就没有管了QAQ
by GGAD @ 2019-10-05 20:35:33
@wangmaohua20090908 我还没太搞懂树状数组其实（小声），请问树状数组和线段树有什么联系之类的吗
by wmy_goes_to_thu @ 2019-10-05 20:37:48
@GGAD 线段树能解决所有树状数组能解决的问题
by GGAD @ 2019-10-05 20:39:57
@wangmaohua20090908 好的谢谢Thanks♪(･ω･)ﾉ那我回去好好研究线段树吧：）
by wmy_goes_to_thu @ 2019-10-05 20:41:26
@GGAD 树状数组代码量小呀，线段树100行下不来
by GGAD @ 2019-10-05 21:14:23
@wangmaohua20090908 哦哦哦是吗我不太了解。。。搞线段树和树状数组洛谷的板子题怎么样啊
by wmy_goes_to_thu @ 2019-10-06 10:13:01
@GGAD 线段树的题，您大佬可以先刷树状数组的模板，四个模板（线段树，树状数组）我都过了，感觉线段树先从树状数组的模板做起很好