/ zzf / 讨论 / 题解 /

火柴排队

#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 条评论

  • 1