题意简化

给定一个正整数

n(1 \le n \le 10^6)

和两个长度为

n

、下标从

1

到

n

的序列

a

、

b

。每次可以选择一个不相等的正整数

i

，且

1 \le i < n

，交换

a_i,a_{i+1}

或交换

b_i,b_{i+1}

。问：在最小化

\sum_{i=1}^{n} (a_i - b_i)^2

的前提下，最少的步数模

10^8 - 3

的结果（原题-P1966）。

暴力简述

注意到，交换

a_i,a_{i+1}

与交换

b_i,b_{i+1}

在计算答案时是等价的。所以，直接暴力枚举即可，没有什么太难的思维难度，代码就不放了。

正解思路及部分代码片段

首先，见【暴力简述】，可以固定一个数组，交换另一个数组中的元素，尽可能的最小化

\sum_{i=1}^{n} (a_i - b_i)^2

。那么我们来想一想，什么情况下这个值会最小呢？比较容易地可以想到：

a,b

序列每个元素的排名相同。即：令

p_i

为

a

数组排序后（此时已经交换完毕）第

i

个元素的下标，

q_i

为

b

数组排序后（此时已经交换完毕）第

i

个元素的下标。则

p_i = q_i \forall 1 \le i \le n

（如有相同，则可任取，只要有一种情况满足即可）。即求：把

p_i

变成

q_i

的最少交换次数模

10^8-3

的结果。那还是不能在

1

秒之内求出答案呀！通过交换相邻元素，使一个序列变成另一个序列，让我们很快就能够想到：逆序对。
在这里解释一下：若有一个长度为

n

的序列

x_i

，则满足

x_i > x_j

且

i < j

的

x_i,x_j(1 \le i, j \le n)

就是一组逆序对。它的逆序对个数

m

的计算方式如下：

\tag{*} m = \sum_{i = 1}^{n} \sum_{j = i + 1}^{n} [x_i > x_j]

（上述公式中

[]

符号的意思：若里面逻辑表达式为真，则返回

1

；否则，返回

0

）。
那么，已知一个序列，该如何求呢？暴力当然很简单，双层循环加判断，统计一下就行了。然而时间复杂度是

O(n^2)

。但是当然可以优化，用归并排序和双指针（可能还有一些其它方法吧 ~~，但是我不会~~）。若需求序列

x

中

l

r

的子段中的逆序对个数，可作以下处理：

F(l,r) = \begin{cases} 0 & l = r \\ F(l, \lfloor \frac{l + r}{2} \rfloor) + F(\lfloor \frac{l + r}{2} \rfloor + 1, r) + G(l,\lfloor \frac{l + r}{2} \rfloor,\lfloor \frac{l + r}{2} \rfloor + 1,r) & l < r \end{cases}

其中，

F(l,r)(l \le r)

表示序列

x

中

l

r

的子段中的逆序对个数（序列

x_l,x_{l+1},x_{l+2},...,x_{r-1},x_r

中的逆序对个数），

G(l_1,r_1,l_2,r_2)(l_1 \le r_1 < l_2 \le r_2)

表示

(*)

式中

i \in [l_1,r_1],j \in [l_2,r_2]

时的结果（这里的

[]

符号表示一段左闭右闭实数区间，但是注意：

i,j

都是整数）。即：

\tag{**} \sum_{i = l_1}^{r_1} \sum_{j = l_2}^{r_2} [x_i > x_j]

（上述公式中

[]

符号的意思：若里面逻辑表达式为真，则返回

1

；否则，返回

0

）。
然而，根据主定理，若有一函数

T(x)

满足其时间复杂度计算方式如下：

T(n) = \begin{cases} \Omicron(1) & n < b \\ a \cdot T(\frac{n}{b}) + f(n) & n \ge b \end{cases}

（表示一个规模为

n

的问题被划分成

a

个规模为

\frac{n}{b}

的子问题，在其他处理时（如合并）的时间复杂度为

f(n)

）
则其时间复杂度的计算方式为：

T(n) = \begin{cases} \Theta(n^{log_b a}) & f(n) = \Omicron(n^{log_b a - \epsilon}), \epsilon > 0 \\ \Theta(f(n)) & f(n) = \Omega(n^{log_b a + \epsilon}), \epsilon \ge 0,\text{且存在一个 } c(c < 1) \text{，使对于满足 } n \ge b \text{ 的 } n \text{ 都有 } a \cdot f(\frac{n}{b}) \le c \cdot f(n) \\ \Theta(n^{log_b a} log^{k + 1} n) & f(n) = \Theta(n^{log_b a} log^k n), k \ge 0 \end{cases}

此时，

a = 2

，

b = 2

，

f(n) = G(n) = \Omicron(\frac{n^2}{4})

，属于上面公式的第二种情况。

\therefore T(n) = \Omicron(f(n)) = \Omicron(\frac{n^2}{4})

（可以看作

\Omicron(n^2)

）。没有起到十分有用的优化。我们发现，时间复杂度的瓶颈是

f(n)

，所以我们需要优化

f(n)

的时间复杂度。接下来就需要用归并排序和双指针了。
如果在合并的时候（

G(l_1,r_1,l_2,r_2)(l_1 \le r_1 < l_2 \le r_2)

），区间

1

（

l_1

r_1

）和区间

2

（

l_2

r_2

）都是单调不下降的，那么在合并的时候，是不是就能优化了呢？
在合并的时候，我们需要做两件事：将两个单调不下降区间（

l_1

r_1

和

l_2

r_2

）合并成一个单调不下降的大区间（

l_1

r_2

）、统计逆序对数量（

(**)

式）。
首先，先看第一件事，将两个单调不下降的区间合并成一个单调不下降的大区间，很容易地就能够想到双指针。下面提供一个例子（片段）：

CPP

int p1 = l1, p2 = l2, p3 = l1;
while(p1 <= r1 && p2 <= r2) {
    if(a[p1] > a[p2]) b[p3++] = a[p2++];
    else b[p3++] = a[p1++];
}
while(p1 <= r1) b[p3++] = a[p1++];
while(p2 <= r2) b[p3++] = a[p2++];
for(int i = l1; i <= r2; i ++) a[i] = b[i];

上面的代码片段完成了将

a

序列中

l_1

r_1

和

l_2

r_2

的两个单调不下降的区间合并成一个

l_1

r_2

的单调不下降的大区间的功能。
第一件事完成了。那么，如何在这个过程中，加入第二件事：统计逆序对数量（

(**)

式）呢？
首先，因为

a

序列中

l_1

r_1

和

l_2

r_2

的两个区间是单调不下降的，所以可以得到：在第一个循环中，若判断语句成立，则不仅

a_{p_1}

（换一种形式写上，理解就行）和

a_{p_2}

是一对逆序对，对于所有满足

i \in [p_1,r_1]

的整数

i

（这里的

[]

符号表示一个左闭右闭实数区间，但是因为

i

是整数，所以在这里也可以理解成一个左闭右闭整数区间），都有

a_i

和

a_{p_2}

是逆序对，共

r_1 + 1 - p_1

对。这样就计算出了这一部分所有的逆序对了。
实际上就是在上面的代码片段中加入一个语句，变成这样：

CPP

int p1 = l1, p2 = l2, p3 = l1;
while(p1 <= r1 && p2 <= r2) {
    if(a[p1] > a[p2]) {
        b[p3++] = a[p2++];
        ans += (r1 + 1 - p1);
    }
    else b[p3++] = a[p1++];
}
while(p1 <= r1) b[p3++] = a[p1++];
while(p2 <= r2) b[p3++] = a[p2++];
for(int i = l1; i <= r2; i ++) a[i] = b[i];

只需要在这个基础上对

10^8 - 3

取模即可。
好了，就这样，我们把

G(n)

的时间复杂度从

\Omicron(\frac{n^2}{4})

优化成了

\Omicron(n)

。
再根据主定理，此时，

a = 2

，

b = 2

，

f(n) = G(n) = \Omicron(n)

，属于上面公式的第三种情况，且

k = 0

。

\therefore T(n) = \Omicron(n^{log_b a} log^{k + 1} n) = \Omicron(n^{log_2 2} log^{0 + 1} n) = \Omicron(n log n)

。
如果想要练习的话，可以做一做模板题-逆序对。
好了，讲了这么多，到底该如何用进这道题目中去呢？首先，肯定要得到

a,b

数组排序后的下标，但是如何知道排序后的下标呢？有不止一种实现方式。
第一种方式：将

a,b

数组定义成机构体，如下：

CPP

struct node {
    int Val, Index;
}a[100010], b[100010];

然后再用一个函数作为排序（快速排序）函数的第三个参数：

CPP

bool cmp(node u, node v) {
    return (u.Val < v.Val);
}

用的时候就这么用：

CPP

sort(a + 1, a + n + 1, cmp);
sort(b + 1, b + n + 1, cmp);

还有第二种方式：用

a,b

数组对

p,q

数组进行排序。
定义很普通：

CPP

int a[100010], b[100010], p[100010], q[100010];

记得初始化：

CPP

for(int i = 1; i <= n; i ++) {
    p[i] = q[i] = i;
}

函数这么写（两个）：

CPP

bool cmpa(int u, int v) {
    return (a[u] < a[v]);
}
bool cmpb(int u, int v) {
    return (b[u] < b[v]);
}

用的时候就这么用：

CPP

sort(p + 1, p + n + 1, cmpa);
sort(q + 1, q + n + 1, cmpb);

反正不管怎么样，排完序之后（离散化）都会得到两个下标数组（a[i].Index 和 b[i].Index、p[i] 和 q[i]）。接下来，再定义一个新数组

c

，用下面的方法来处理：
第一种方式：

CPP

for(int i = 1; i <= n; i ++) {
    c[a[i].Index] = b[i].Index;
//  c[b[i].Index] = a[i].Index;
}

第二种方式：

CPP

for(int i = 1; i <= n; i ++) {
    c[p[i]] = q[i];
//  c[q[i]] = p[i];
}

反正不管怎么样，现在都会得到一个

c

数组，答案就是对

c

数组计算逆序对个数然后对

10^8 - 3

取模（将

c

数组变成

c_i = i \forall 1 \le i \le n

的形式所要用的最少步数对

10^8 - 3

取模）。
就这样，这道看似很难的题就被解决了。

代码

最后再补充一点，再之前讲合并函数的时候，形参一共有四个。但是不难发现，实际上并不需要四个，可以只有三个甚至两个，我个人习惯用三个形参的方式来实现，这并不代表其它方式就不行了，仅限个人习惯。好了，上代码。
第一种实现方式：

CPP

#include <bits/stdc++.h>
using namespace std;
const int Mod = 99999997;
int n, ans, c[100010], d[100010];
struct node {
    int Val, Index;
}a[100010], b[100010];
bool cmp(node u, node v) {
    return (u.Val < v.Val);
}
void Merge(int l, int mid, int r) {
    int p1 = l, p2 = mid + 1, p3 = l;
    while(p1 <= mid && p2 <= r) {
        if(c[p1] > c[p2]) {
            d[p3++] = c[p2++];
            ans = (ans + mid + 1 - p1) % Mod;
        }
        else d[p3++] = c[p1++];
    }
    while(p1 <= mid) d[p3++] = c[p1++];
    while(p2 <= r) d[p3++] = c[p2++];
    for(int i = l; i <= r; i ++) {
        c[i] = d[i];
    }
}
void Sort(int l, int r) {
    if(l == r) return;
    int mid = (l + r) >> 1;
    Sort(l, mid);
    Sort(mid + 1, r);
    Merge(l, mid, r);
}
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) {
        scanf("%d", &a[i].Val);
        a[i].Index = i;
    }
    for(int i = 1; i <= n; i ++) {
        scanf("%d", &b[i].Val);
        b[i].Index = i;
    }
    sort(a + 1, a + n + 1, cmp);
    sort(b + 1, b + n + 1, cmp);
    for(int i = 1; i <= n; i ++) {
        c[a[i].Index] = b[i].Index;
    }
    Sort(1, n);
    printf("%d", ans);
    return 0;
}

第二种实现方式：

CPP

#include <bits/stdc++.h>
using namespace std;
const int Mod = 99999997;
int n, ans, a[100010], b[100010], c[100010], d[100010], p[100010], q[100010];
bool cmpa(int u, int v) {
    return (a[u] < a[v]);
}
bool cmpb(int u, int v) {
    return (b[u] < b[v]);
}
void Merge(int l, int mid, int r) {
    int p1 = l, p2 = mid + 1, p3 = l;
    while(p1 <= mid && p2 <= r) {
        if(c[p1] > c[p2]) {
            d[p3++] = c[p2++];
            ans = (ans + mid + 1 - p1) % Mod;
        }
        else d[p3++] = c[p1++];
    }
    while(p1 <= mid) d[p3++] = c[p1++];
    while(p2 <= r) d[p3++] = c[p2++];
    for(int i = l; i <= r; i ++) {
        c[i] = d[i];
    }
}
void Sort(int l, int r) {
    if(l == r) return;
    int mid = (l + r) >> 1;
    Sort(l, mid);
    Sort(mid + 1, r);
    Merge(l, mid, r);
}
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) {
        scanf("%d", &a[i]);
        p[i] = i;
    }
    for(int i = 1; i <= n; i ++) {
        scanf("%d", &b[i]);
        q[i] = i;
    }
    sort(p + 1, p + n + 1, cmpa);
    sort(q + 1, q + n + 1, cmpb);
    for(int i = 1; i <= n; i ++) {
        c[p[i]] = q[i];
    }
    Sort(1, n);
    printf("%d", ans);
    return 0;
}

数据通过情况

第一种实现方式
第二种实现方式

最后的话

一定一定不要 Copy 代码！！！ 并且最好不要边看边写。应该先理解每一步在做什么，对代码有了一个清晰的认识，在自己手打一遍，加深印象。本文中的代码仅供参考，不喜勿喷。
最后的最后，写篇文章不容易，可否来个赞？？？

P1966题解

文章操作