P1966题解

· · 题解

题意简化

给定一个正整数 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）、统计逆序对数量（(**) 式）。
首先，先看第一件事，将两个单调不下降的区间合并成一个单调不下降的大区间，很容易地就能够想到双指针。下面提供一个例子（片段）： 

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

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 数组定义成机构体，如下： 

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

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

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

用的时候就这么用： 

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

还有第二种方式：用 a,b 数组对 p,q 数组进行排序。
定义很普通： 

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

记得初始化： 

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

函数这么写（两个）： 

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

用的时候就这么用： 

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，用下面的方法来处理：
第一种方式： 

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

第二种方式： 

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 取模）。
就这样，这道看似很难的题就被解决了。

代码

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

#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;
}

第二种实现方式： 

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