- 题解
- 2018-09-17 18:03:37 @
#include <cstdio>
#include <cstring>
#include <algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define mo 99999997
using namespace std;
const int N=100005;
struct node{
int val;
int id;
}first[N],second[N];
bool cmp(node a,node b){
return (a.val<b.val);
}
int n,a[N],b[N],ans=0;
//核心:归并求逆序对
void msort(int l,int r){
if (l>=r) return;
int mid=(l+r)>>1;
msort(l,mid);msort(mid+1,r);
int i=l,k=l,j=mid+1;
while(i<=mid && j<=r){
if (a[i]>a[j]){
b[k++]=a[j++];
ans+=mid-i+1;//就它求了逆序和
ans%=mo;
}
else b[k++]=a[i++];
}
while (i<=mid){
b[k++]=a[i++];
}
while (j<=r){
b[k++]=a[j++];
}
For(i,l,r) a[i]=b[i];
}
int main()
{
scanf("%d",&n);
For(i,1,n) scanf("%d",&first[i].val),first[i].id=i;
For(i,1,n) scanf("%d",&second[i].val),second[i].id=i;
sort(first+1,first+n+1,cmp);
sort(second+1,second+n+1,cmp);
For(i,1,n) a[first[i].id]=second[i].id;
msort(1,n);
printf("%d\n",ans);
return 0;
}
1 条评论
-
PA_lotusbl LV 5 MOD @ 2018-09-17 18:04:09
lalalalala
- 1