2013年NOIP全国联赛提高组 ### 1039: 火柴排队

思路：

​ 我们只需保证交换后左边的第K大跟右边的第K大在同一个位置即可。对于左边数组A，右边的数组为B，数组B中第i个数是第k大，所以我们需要把A数组中第k大的数放到第i个。根据这样可以构造一个数组，数组中第 $i$i 个值 $a\left[i\right]$a[i] 代表数组A中第 $i$i 个数是第k大，且B数组中第k大的位置是 $a\left[i\right]$a[i]

故我们求逆序数即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll A[100005],B[100005],pos[100005],seq[100005];
ll sa[100005],sb[100005];
ll sum;
ll marr[100005];
void mergeSort(ll *arr,ll l,ll r)
{
    if(l==r) return ;
    ll mid=(l+r)/2;
    mergeSort(arr,l,mid);
    mergeSort(arr,mid+1,r);
    ll tot=0;
    ll LL=l,rr=mid+1;
    while(LL<=mid&&rr<=r)
    {
        if(arr[rr]<arr[LL])
        {
            sum+=mid-LL+1;
            marr[tot++]=arr[rr++];
        }
        else
        {
            marr[tot++]=arr[LL++];
        }
    }
    for(ll i=LL; i<=mid; ++i) marr[tot++]=arr[i];
    for(ll i=rr; i<=r; ++i)  marr[tot++]=arr[i];
    for(ll i=0; i<r-l+1; ++i) arr[l+i]=marr[i];
    return ;
}
int main()
{
    ll cas=0;
    n=10;
    while(~scanf("%lld",&n))
    {
        if(cas) puts("");
        cas=1;
        for(ll i=1; i<=n; ++i) {scanf("%lld",A+i);sa[i]=A[i];}
        for(ll i=1; i<=n; ++i) {scanf("%lld",B+i);sb[i]=B[i];}
        sort(sa+1,sa+n+1);
        sort(sb+1,sb+n+1);
        for(ll i=1; i<=n; ++i)
        {
            ll th=lower_bound(sb+1,sb+1+n,B[i])-sb;
            pos[th]=i;
        }
        for(ll i=1; i<=n; ++i)
        {
            ll th=lower_bound(sa+1,sa+1+n,A[i])-sa;
            seq[i]=pos[th];
        }
        sum=0;
        mergeSort(seq,1,n);
        cout<<sum%99999997<<endl;
    }
    return 0;
}