一列固定，另一列按其顺序做归并排序逆序对。。
所谓归并排序逆序对，就是在归并排序的时候可以顺便把逆序对给统计了。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
// <match.cpp> - 02/09/16 18:32:47 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } struct num{ int n,id; }a[100001],b[100001]; int q[100001],yx[100001]; long long ans; void merge(int l,int r){ if(l>=r)return; int m=(l+r)>>1; merge(l,m);merge(m+1,r); int i=l,j=m+1,k=l; while(i<=m&&j<=r){ if(q[i]>q[j]){ yx[k++]=q[j++]; ans=(ans+m-i+1)%99999997; } else yx[k++]=q[i++]; } while(i<=m)yx[k++]=q[i++]; while(j<=r)yx[k++]=q[j++]; for(int w=l;w<=r;w++)q[w]=yx[w]; } int cmp(num a,num b){return a.n<b.n;} int main(){ freopen("match.in","r",stdin); freopen("match.out","w",stdout); int n=getint(); for(int i=0;i<n;i++)a[i].n=getint(),a[i].id=i; for(int i=0;i<n;i++)b[i].n=getint(),b[i].id=i; sort(a,a+n,cmp); sort(b,b+n,cmp); for(int i=0;i<n;i++)q[a[i].id]=b[i].id; merge(0,n-1); cout<<ans; return 0; } |