ARC 补题目录

一道不错的构造题。
把长度为 $2n$ 的序列先拆成 $a$ 和 $b$。

设 $a$ 中最小值为 $Mina$，$b$ 中 $Mina$ 对应的最小值为 $Minb$。
那么如果 $Minb \lt Mina$，显然一对 $(Mina, Minb)$ 是最优解。

否则显然要选择所有的 $Mina$，再考虑后面的加入会不会让字典序变小。

设 $Mina$ 第一次出现的下标是 $fi$，最后一次出现是 $p$。
则每次我们需要在 $[p+1,n]$ 中选择一个数 $x$ 满足 $a_{x} \lt b_{fi}$，才能让字典序更小，同时更新 $p=x$。
这个操作用线段树或者 ST 表等都可以解决。

然后我写完没有 CE，样例都是一发过，交了一下 WA 了。

手玩样例：

a: 1 1 2
b: 2 3 1

我们目前的思路是输出 1 1 2 3，但其实 a[3] b[3] 选择后会更优。

那么我们记录一个 se（second） 表示 $b_{fi}$ 之后第一个和它不同的数（要保证 $a_{sec}=Mina$）。
只要 $a_x \gt b_{fi}$ 或者 $a_x = b_{fi}$ 且 $b_{fi} \gt b_{se}$ 就说明不用更新了，其他情况继续加入。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15;
int n, a[N], b[N], Mina, Minb;
int fi, se;

struct Tree {
    int l, r;
    int Min;    //存储下标
} tr[N << 2];
void pushup(int u) {
    int x = tr[u << 1].Min, y = tr[u << 1 | 1].Min;
    if (a[x] <= a[y]) tr[u].Min = x;
    else tr[u].Min = y;
}
void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if (l == r) {
        tr[u].Min = l;
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
int query(int u, int l, int r) {
    if (l > r) return 0;
    if (tr[u].r < l || tr[u].l > r) return 0;
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].Min;
    int x = query(u << 1, l, r);
    int y = query(u << 1 | 1, l, r);
    if (a[x] <= a[y]) return x;
    else return y;
}

int ans[N], tot = 0;

int main() {
    scanf("%d", &n);
    Mina = Minb = 0x3f3f3f3f;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), Mina = min(Mina, a[i]);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
        if (a[i] == Mina) {
            if (!fi) fi = i;    //第一次出现
            Minb = min(Minb, b[i]);
            if (!se && fi && b[i] != b[fi]) se = i;
        }
    }
    // cout << '\t' << fi << ' ' << se << endl;
    if (Minb <= Mina) return printf("%d %d\n", Mina, Minb), 0;
    a[0] = b[0] = 0x3f3f3f3f;
    build(1, 1, n);
    int p = 0;
    for (int i = 1; i <= n; i++)
        if (a[i] == Mina) ans[++tot] = i, p = i;
    p++;
    while (p <= n) {
        int x = query(1, p, n);
        if (x == 0 || a[x] > b[fi]) break;
        if (a[x] == b[fi] && (!se || b[fi] > b[se])) break;
        ans[++tot] = x;
        p = x + 1;
    }
    for (int i = 1; i <= tot; i++) printf("%d ", a[ans[i]]);
    for (int i = 1; i <= tot; i++) printf("%d ", b[ans[i]]);
    return 0;
}