- 火柴排队
- 2016-09-27 23:24:56 @
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100000+5;
const int M=99999997;
int a[maxn],b[maxn],ra[maxn],rb[maxn],r[maxn],t[maxn],n,cnt;
bool cmpa(const int i,const int j){
return a[i]<a[j];
}
bool cmpb(const int i,const int j){
return b[i]<b[j];
}
void build(){
for(int i=1;i<=n;i++){
ra[i]=i;
rb[i]=i;
}
sort(ra,ra+n,cmpa);
sort(rb,rb+n,cmpb);
for(int i=0;i<n;i++) t[ra[i]-1]=i;
for(int i=0;i<n;i++) r[i]=t[rb[i]-1];
memset(t,0,sizeof(t));
}
void merge_sort(int x,int y){
if(y-x<=1) return;
int m=x+(y-x)/2;
int p=x,q=m,i=x;
merge_sort(x,m);
merge_sort(m,y);
while(p<m||q<y){
if(q>=y||(p<m&&r[p]<=r[q])) t[i++]=r[p++];
else{
t[i++]=r[q++];
cnt=(cnt+m-p)%M;
}
}
for(i=x;i<y;i++) r[i]=t[i];
}
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
build();
merge_sort(0,n-1);
cout<<cnt<<endl;
return 0;
}
0 条评论
目前还没有评论...
信息
- ID
- 1842
- 难度
- 7
- 分类
- (无)
- 标签
- 递交数
- 5085
- 已通过
- 1102
- 通过率
- 22%
- 被复制
- 10
- 上传者