我一年前甚至不会做/qd
发现 \(a_{x_1}\) 为 \(k = \min\limits_{i=1}^n a_i\) 时最优。然后开始分类讨论：
- 如果 \(\min\limits_{a_i = k} a_{i+n} \le k\)，答案为 \((k, \min\limits_{a_i = k} a_{i+n})\)。这是因为如果再选一个 \(k\) 肯定不优。
- 否则我们肯定尽可能先把 \(k\) 选完。接下来讨论最后一个 \(k\) 的位置直到 \(n\) 还能不能再选。设 \(p\) 为第一个 \(a_p = k\) 的位置。
- 每次选的数要保证 \(\le a_{p+n}\) 且是当前区间内的最小值，不然不优。
- 当当前区间内最小值 \(= a_{p+n}\) 时有些特殊。如果 \(a_{p+n}\) 大于它后面被选的第一个 \(\ne a_{p+n}\) 的数，或者它后面不存在 \(\ne a_{p+n}\) 的数，那么选了这个区间最小值也不优。
实现时使用 ST 表查询区间最小值，复杂度 \(O(n \log n)\)。
code
// Problem: D - Concatenate Subsequences
// Contest: AtCoder - AtCoder Regular Contest 134
// URL: https://atcoder.jp/contests/arc134/tasks/arc134_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 200100;
const int logn = 20;
const int inf = 0x3f3f3f3f;
int n, a[maxn], lg[maxn];
pii f[maxn][logn];
inline pii qmin(int l, int r) {
int k = lg[r - l + 1];
return min(f[l][k], f[r - (1 << k) + 1][k]);
}
void solve() {
scanf("%d", &n);
for (int i = 2; i <= n * 2; ++i) {
lg[i] = lg[i >> 1] + 1;
}
for (int i = 1; i <= n * 2; ++i) {
scanf("%d", &a[i]);
if (i <= n) {
f[i][0] = make_pair(a[i], i);
}
}
for (int j = 1; (1 << j) <= n; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
int mn = *min_element(a + 1, a + n + 1), pos = -1, t = inf;
for (int i = 1; i <= n; ++i) {
if (a[i] == mn) {
t = min(t, a[i + n]);
}
}
if (t <= mn) {
printf("%d %d\n", mn, t);
return;
}
vector<int> vc, tv;
for (int i = 1; i <= n; ++i) {
if (a[i] == mn) {
vc.pb(i);
pos = i;
tv.pb(a[i + n]);
}
}
int x = -1;
for (int i = 0; i < (int)tv.size(); ++i) {
if (tv[i] != tv[0]) {
x = tv[i];
break;
}
}
while (pos < n) {
pii p = qmin(pos + 1, n);
if (p.fst > tv[0] || (p.fst == tv[0] && tv[0] > x)) {
break;
}
vc.pb(p.scd);
pos = p.scd;
}
for (int x : vc) {
printf("%d ", a[x]);
}
for (int x : vc) {
printf("%d ", a[x + n]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}