Luogu | P1966 [NOIp 2013] 火柴排队 | 数据结构 | 树状数组

Description

涵涵有两盒火柴，每盒装有 $n$ 根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为：$\sum (a_i-b_i)^2$。

其中 $a_i$ 表示第一列火柴中第 $i$ 个火柴的高度，$b_i$ 表示第二列火柴中第 $i$ 个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 $99,999,997$ 取模的结果。

Input Format

共三行，第一行包含一个整数 $n$，表示每盒中火柴的数目。

第二行有 $n$ 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。

第三行有 $n$ 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。

Output Format

一个整数，表示最少交换次数对 $99,999,997$ 取模的结果。

Input Sample

Sample 01

4
2 3 1 4
3 2 1 4

Sample 02

4
1 3 4 2
1 7 2 4

Output Sample

Sample 01

1

Sample 02

2

Data Range

$1 \le N \le 10^5$，火柴高度在 long long 范围内。

Solution

考虑将距离的式子化开，无论 $a_i$ 和 $b_i$ 怎么选，最后总和里 $a_i^2$ 和 $b_i^2$ 都不会变，所以直接看 $-2ab$ 的部分。则题目要求 $\sum2ab$ 最大。数学方法可证得当 $A,B$ 两个序列均按相同（升序 / 降序）排序时值最大。

显然交换 $A$ 和交换 $B$ 等价，所以只考虑将 $B$ 作为基准映射 $A$ 之后交换 $A$。树状数组求逆序对。

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

#define mod 99999997
#define lowbit(x) (x&(-x))

using std::sort;
using std::lower_bound;

typedef long long ll;

inline void Read(int &x){
    x=0; char ch=0; while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return;
}

struct data{
    int id;
    ll val;
    int ExceptedPosition;
    friend bool operator < (data a,data b){
        return a.val<b.val;
    } 
}A[100005],B[100005];

int N;

ll ans;

int BIT[100005];

ll pool[200005];

bool rec(data a,data b){
    return a.id<b.id;
}

void BITModify(int u,int v){
    for(;u<=N;u+=lowbit(u))
        BIT[u]+=v;
    return;
}

int BITQuery(int u){
    int ret=0;
    for(;u;u-=lowbit(u))
        ret+=BIT[u];
    return ret;
}

int BITQuery(int L,int R){
    return BITQuery(R)-BITQuery(L-1);
}

int main(){
    Read(N);
    rep(i,1,N)
        scanf("%lld",&A[i].val);
    rep(i,1,N)
        scanf("%lld",&B[i].val);
    rep(i,1,N)
        pool[i]=A[i].val;
    rep(i,1,N)
        pool[i+N]=B[i].val;
    rep(i,1,N)
        A[i].id=i,B[i].id=i;
    sort(pool+1,pool+1+2*N);
    rep(i,1,N)
        A[i].val=lower_bound(pool+1,pool+1+2*N,A[i].val)-pool;
    rep(i,1,N)
        B[i].val=lower_bound(pool+1,pool+1+2*N,B[i].val)-pool;
    sort(A+1,A+1+N);
    sort(B+1,B+1+N);
    rep(i,1,N)
        A[i].ExceptedPosition=B[i].id;
    sort(A+1,A+1+N,rec);
    rep(i,1,N){
        ans+=BITQuery(A[i].ExceptedPosition,N);
        BITModify(A[i].ExceptedPosition,1);
    }
    printf("%lld\n",ans%mod);
    return 0;
}