LGOJ P1966 火柴排队

LGOJ P1966 火柴排队

给定两个数组，对之一进行相邻元素的移动使得：
\[\sum (a_i-b_i)^2\]
最小。
对原式做变形：
\[\sum (a_i^2+b_i^2-2a_ib_i)\\\\\\=\sum a_i^2 +\sum b_i^2 -2\sum a_ib_i\]
求\((\sum (a_i-b_i)^2)_{min}\)即求\((\sum a_ib_i)_{max}\)

由排序不等式：
\[a_1b_n+a_2b_{n-1}+a_3b_{n-2}+...+a_nb_1 \leq a_{p_1}b_{q_1} +a_{p_2}b_{q_2}+a_{p_3}b_{q_3}+...+a_{p_n}b_{q_n} \leq a_1b_1+a_2b_2+a_3b_3+...+a_nb_n, \\ \forall i<j \in [1,n],a_i<a_j,b_i<b_j\]
也即逆序和小于乱序和小于顺序和，我们要求的就是将a序列变成相对b有序需要交换相邻元素的最小次数。

—未完待续……

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1000005,mod=99999997;
inline ll read()
{
    char c=getchar();ll x=0;
    for(;!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar())
        x=x*10+c-'0';
    return x;
}
ll n,c[N];
ll cnt;
ll ls[N];
struct L
{
    int val,ind;
};

L l1[N],l2[N];
inline bool cmp(L i,L j)
{
    return i.val<j.val;
}

void mgs(ll l,ll r)
{
    if(l==r)return;
    ll mid=(l+r)/2;
    mgs(l,mid);
    mgs(mid+1,r);
    ll i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r)
    {
        if(c[i]>c[j])
        {
            ls[k++]=c[j++];
            cnt=(cnt+mid-i+1)%mod;
        }
        else
        {
            ls[k++]=c[i++];
        }
    }
    while(i<=mid)ls[k++]=c[i++];
    while(j<=r)ls[k++]=c[j++];
    for(ll i=l;i<=r;i++)c[i]=ls[i];
}


int main()
{
    //freopen("C:\\Users\\Administrator\\Downloads\\testdata (9).in","r",stdin);
    cin>>n;
    for(ll i=1;i<=n;i++)l1[i].ind=i,l1[i].val=read();
    for(ll i=1;i<=n;i++)l2[i].ind=i,l2[i].val=read();
    sort(l1+1,l1+n+1,cmp);
    sort(l2+1,l2+n+1,cmp);
    for(ll i=1;i<=n;i++)c[l1[i].ind]=l2[i].ind;

    mgs(1,n);
    cout<<cnt;

    return 0;
}