把代码整理好再问，用插入代码，不要直接粘贴
by 陈曦 @ 2018-07-19 16:55:47
@[陈曦](/space/show?uid=57026) ```cpp
#include <iostream>
#include <algorithm>
using namespace std;
const int SIZE=1000010;
int temp[SIZE];
int ans=0;
struct no{
long long h;
int pre;
}a[SIZE],b[SIZE];
bool cmp(const struct no &a,const struct no &b){
return a.h<b.h;
}
void merge(int l,int mid,int r){
int L[SIZE],R[SIZE];
int len_L=mid-l+1;
int len_R=r-mid;
for (int i=1;i<=len_L;i++)L[i]=temp[l+i-1];
for (int i=1;i<=len_R;i++)R[i]=temp[mid+i];
for (int i=1,j=1,k=l;k<=r;k++){
if (i>len_L)temp[k]=R[j++];
else if (j>len_R)temp[k]=L[i++];
else{
if (L[i]<=R[j])temp[k]=L[i++];
else{
ans+=len_L-i+1;
temp[k]=R[j++];
}
}
}
}
void merge_sort(int l,int r){
if (l<r){
int mid=(l+r)/2;
merge_sort(l,mid);
merge_sort(mid+1,r);
merge(l,mid,r);
}
}
int main(){
int n;
cin>>n;
for (int i=1;i<=n;i++){cin>>a[i].h;a[i].pre=i;}
for (int i=1;i<=n;i++){cin>>b[i].h;b[i].pre=i;}
sort(a+1,a+1+n,cmp);
sort(b+1,b+1+n,cmp);
for (int i=1;i<=n;i++)temp[b[i].pre]=a[i].pre;
//for (int i=1;i<=n;i++)cout<<temp[i]<<endl;
merge_sort(1,n);
cout<<ans<<endl;
return 0;
}
不好意思之前没有发过
by hkr04 @ 2018-07-19 17:00:52
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
const int SIZE=1000010;
int temp[SIZE];
int ans=0;
struct no{
long long h;
int pre;
}a[SIZE],b[SIZE];
bool cmp(const struct no &a,const struct no &b){
return a.h<b.h;
}
void merge(int l,int mid,int r){
int L[SIZE],R[SIZE];
int len_L=mid-l+1;
int len_R=r-mid;
for (int i=1;i<=len_L;i++)L[i]=temp[l+i-1];
for (int i=1;i<=len_R;i++)R[i]=temp[mid+i];
for (int i=1,j=1,k=l;k<=r;k++){
if (i>len_L)temp[k]=R[j++];
else if (j>len_R)temp[k]=L[i++];
else{
if (L[i]<=R[j])temp[k]=L[i++];
else{
ans+=len_L-i+1;
temp[k]=R[j++];
}
}
}
}
void merge_sort(int l,int r){
if (l<r){
int mid=(l+r)/2;
merge_sort(l,mid);
merge_sort(mid+1,r);
merge(l,mid,r);
}
}
int main(){
int n;
cin>>n;
for (int i=1;i<=n;i++){cin>>a[i].h;a[i].pre=i;}
for (int i=1;i<=n;i++){cin>>b[i].h;b[i].pre=i;}
sort(a+1,a+1+n,cmp);
sort(b+1,b+1+n,cmp);
for (int i=1;i<=n;i++)temp[b[i].pre]=a[i].pre;
//for (int i=1;i<=n;i++)cout<<temp[i]<<endl;
merge_sort(1,n);
cout<<ans<<endl;
return 0;
}
```@[陈曦](/space/show?uid=57026)
by hkr04 @ 2018-07-19 17:01:58
不要轻易相信他给的范围，有很多题目数据都是毒瘤，不过比赛就好一些。但是这题应该1000010够了，是re了吗
by 陈曦 @ 2018-07-19 17:06:05
@[陈曦](/space/show?uid=57026) 不是，结果错了，有一个出现负数。把输入下载下来看了以后发现给出的n是10000082112，估计这个点是因为数组开得不够大。还有一个点的结果相差很大
by hkr04 @ 2018-07-19 17:54:20
@[陈曦](/space/show?uid=57026) Σ（ﾟдﾟlll）换了台电脑发现显示正常了，是n和第一个数连一起了……还是想请教一下怎么优化可以嘛？
by hkr04 @ 2018-07-19 21:25:32
@[_Hyde_](/space/show?uid=111528) 你是怎么wa的，是答案错了吧
by 陈曦 @ 2018-07-19 21:29:11
可以自己调
by 陈曦 @ 2018-07-19 21:30:39
你取模了吗，大哥
by 陈曦 @ 2018-07-19 21:32:21
还有要把temp开到long，以后记得仔细看题
by 陈曦 @ 2018-07-19 21:41:39