【1】题解：P1966 [NOIP2013 提高组] 火柴排队【树状数组】【数据结构】【逆序对】

· · 题解

题目有一个式子：\sum_{i=1}^n(a_i-b_i)^2。

我们拆一下，原式变为 \sum_{i=1}^n a_i^2-2a_ib_i+b_i^2。

再拆一次，得 \sum_{i=1}^n a_i^2 + \sum_{i=1}^n b_i^2 - 2\sum_{i=1}^n a_ib_i。

显然，让 \sum_{i=1}^n(a_i-b_i)^2 最小化，就要让 \sum_{i=1}^n a_ib_i 最大化。

我们发现，排完序后，\sum_{i=1}^n a_ib_i 最大化。

之后逆序对即可通过。

//2022tysc0819
#include<bits/stdc++.h>
//#include<bits/extc++.h>
using namespace std;
//using namespace __gnu_pbds;
//#define arr array<int,3>
#define int long long
//#define pb push_back
//#define double long double
//#define map unordered_map
//#pragma GCC optimize(2,3,"Ofast","inline")
const int N=2e5+10,M=1010,P=99999997,MOD=998244353;
const double PI=3.1415926,EPS=0.00001;
struct nid{int v,i;}a[N],b[N];
bool operator<(nid x,nid y){return x.v<y.v;}
int n,tr[N],su,ans,r[N];
int lb(int x){return x&-x;}
void upd(int p,int x){for(int i=p;i<=n;i+=lb(i))tr[i]+=x;}
int s(int x){su=0;for(int i=x;i>0;i-=lb(i)){su+=tr[i];}return su;}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].v,a[i].i=i;
    for(int i=1;i<=n;i++)cin>>b[i].v,b[i].i=i;
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)r[b[i].i]=a[i].i;
    for(int i=1;i<=n;i++){
        upd(r[i],1);
        ans=(ans+i-s(r[i])+P)%P;
    }
    cout<<ans;
    return 0;
}
//note: