题解 | #[NOIP2013]火柴排队#

思路

稍微用点群论的知识，我们可以感觉出它要我们求逆序对。
于是我们可以先把a和b的数字和离散化结果记录下来，然后用x存储置换后的结果，
然后套个归并排序的板子就OK啦。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
const int mod=1e8-3;

struct node{
    int num,id;
}a[maxn],b[maxn];

int n,x[maxn],t[maxn],ans;

bool cmp(node a,node b){
    return a.num<b.num;
}

void mergesort(int l,int r){
    if(l==r) return;
//    cout<<l<<" "<<r<<endl;
    int mid=l+r>>1;
    mergesort(l,mid);
    mergesort(mid+1,r);
    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r){
        if(x[i]<=x[j]) t[k++]=x[i++];
        else{
            ans=(ans+mid-i+1)%mod;
            t[k++]=x[j++];
        }
    }
    while(i<=mid) t[k++]=x[i++];
    while(j<=r) t[k++]=x[j++];
    for(int p=l,q=0;p<=r;p++,q++) x[p]=t[q];
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].num;
        a[i].id=i;
    }
    for(int i=1;i<=n;i++){
        cin>>b[i].num;
        b[i].id=i;
    }
    sort(a+1,a+1+n,cmp);
    sort(b+1,b+1+n,cmp);
    for(int i=1;i<=n;i++) x[b[i].id]=a[i].id;
    mergesort(1,n);
    cout<<ans<<endl;
    return 0;
}