题解：AT_arc149_b [ARC149B] Two LIS Sum

· · 题解

ARC149 B 题解

Problem

给你两个 1\sim N 的排列，记为数组 A 和 B，每次允许你同时交换 A_i,A_{i+1} 和 B_i,B_{i+1}，其中 i 满足 1\leqslant i\leqslant N-1，问你两数组最长上升子序列长度之和最大值。

Solution

首先我们要证明一个事：那就是无论怎么操作，先把一个数组排好序再对另一个数组求 LIS 长度始终是最优的。

以下证明过程都是假设代码中对 A 排序的，排序完后的 B 记为 B'。

我们取任意操作后的数组 A 和 B，假设它们 \operatorname{LIS} 的交集有 k 个数，则 B 中不属于此交集的共有 \operatorname{LIS}(B)-k 个数，而这些数又一定会出现在 A 中此交集的补集之中，这个补集的大小为 N-\operatorname{LIS}(A)，所以

\operatorname{LIS}(B)-k\leqslant N-\operatorname{LIS}(A)

，即

\operatorname{LIS}(A)+\operatorname{LIS}(B)\leqslant k+N

。

那么问题就转化为求 k 的最大值了。我们利用我们惊人的注意力发现，这 k 个数在 A 中原本就是按从小到大的顺序的，因此上，当我们把 A 排序之后，这 k 个数的相对顺序是不会变的。又因为 A 和 B 这两个数组是互相锁定（即 A_i 确定充分必要于 B_i 确定）的，所以这 k 个数在 B 中原本也是按顺序的，那么在对 A 排序之后它们依旧保持从小到大，也就是：

k\leqslant\operatorname{LIS}(B')

，所以

\operatorname{LIS}(A)+\operatorname{LIS}(B)\leqslant k+N\leqslant\operatorname{LIS}(B')+N

，证毕。

Implementation

先对 A 排序，然后用 O(n\log n) 做法求 \operatorname{LIS}(B)。其实反过来不用了，但是我还是写了。

Code

AC Record 

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;

int n;

struct node {
    int a, b;
} s[N], t[N];

bool cmpa(node x, node y) {
    return x.a < y.a;
}

bool cmpb(node x, node y) {
    return x.b < y.b;
}

int lis[N];

// s: 备份数组，不动 
// t: 实际数组，操作 

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &s[i].a);
    for (int i = 1; i <= n; i++)
        scanf("%d", &s[i].b);
    int ans = -1;
    for (int i = 1; i <= n; i++)
        t[i] = s[i];
    sort(t + 1, t + 1 + n, cmpb);
    memset(lis, 0, sizeof(lis));
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (i == 1 || t[i].a > lis[cnt]) {
            lis[++cnt] = t[i].a;
        }
        else {
            // upper_bound 返回第一个大于的 
            int pos = upper_bound(lis + 1, lis + 1 + cnt, t[i].a) - lis;
            lis[pos] = t[i].a;
        }
    }
    ans = max(ans, n + cnt);
    for (int i = 1; i <= n; i++)
        t[i] = s[i];
    sort(t + 1, t + 1 + n, cmpa);
    memset(lis, 0, sizeof(lis));
    cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (i == 1 || t[i].b > lis[cnt]) {
            lis[++cnt] = t[i].b;
        }
        else {
            // upper_bound 返回第一个大于的 
            int pos = upper_bound(lis + 1, lis + 1 + cnt, t[i].b) - lis;
            lis[pos] = t[i].b;
        }
    }
    ans = max(ans, n + cnt);
    printf("%d", ans);
    return 0;
}