P6891 [JOISC2020] ビルの飾り付け 4
Problem
给定长度为 \(2n\) （\(1\le n\le5\times10^5\)）的序列 \(A\)，\(B\)。要求构造一个单调不降的序列 \(C\)。每个 \(C_i\) 从 \(A_i\) 和 \(B_i\) 中选取，且 \(A\)，\(B\) 中都恰好选取 \(n\) 个。
Solution
最直接的想法显然是 dp ，设 \(f_{i,j,0/1}\) 表示考虑了 \(C\) 的前 \(i\) 位，选了 \(j\) 个 \(A\) 中的，第 \(i\) 位选的是 \(A_i\)/\(B_i\) 是否可行。
但这样设计状态很明显时空复杂度都是会爆的。
这里用一个很经典的技巧——交换 dp 数组的定义域和值域，也就是交换下标和值。
考虑 \(dp_{i,0/1}\) 表示考虑了 \(C\) 的前 \(i\) 位，第 \(i\) 位选 \(A_i\)/\(B_i\) 时选 \(A\) 中元素个数的可行集合，也就是使 \(f_{i,j,0/1}\) 成立的 \(j\) 的集合。
普通的集合是很难转移的，但如果这恰好是区间的话那就可以用左右端点来表示和转移。所以我们尝试能不能证明 \(dp\) 数组表示的是区间。
先想想怎么转移，\(dp_{i,0/1}\) 显然由 \(dp_{i-1,0}\) 和 \(dp_{i-1,1}\) 转移过来，要么是他们的并集，要么是其中一个，可能再整体加一。
再来看 \(dp\) 数组的边界，显然 \(dp_{1,0}=\{1\}\)，\(dp_{1,1}=\{0\}\)，都是区间。而 \(A_1\) 和 \(B_i\) 中大的那个的可行集合一定包含小的那个的可行集合。所以 \(\{x|x-1\in dp_{i,0}\}\) 和 \(dp_{i,1}\) 一定是包含关系，故若两者都是区间，则一定相邻或相交，两者取并也是区间。
这样我们就可以用左右端点来表示 \(dp\) 数组的值。
AC Code
#include <bits/stdc++.h>
namespace _default{
using namespace std;
#define lovely return
#define _lzy_ 0
#define LL long long
#define int long long
#define DB double
#define PII std::pair<int, int>
#define X first
#define Y second
#define uF(i, x, y) for(int i = (x); i <= (y); ++ i)
#define uf(i, x, y) for(int i = (x); i < (y); ++ i)
#define dF(i, x, y) for(int i = (x); i >= (y); -- i)
#define df(i, x, y) for(int i = (x); i > (y); -- i)
#define ef(i, u) for(int i = head[(u)]; i; i = ne[i])
#define sett(x, y) memset(x, y, sizeof x)
#define copy(x, y) memcpy(x, y, sizeof x)
const int MOD = 1e9 + 7;
const DB EPS = 1e-8, INF = 0x3f3f3f3f;
template<typename T> inline T read(){
T s = 0; int f = 0; char ch = getchar();
while(!isdigit(ch)){if(ch == '-') f = 1; ch = getchar();}
while(isdigit(ch)) s = s * 10 + ch - 48, ch = getchar();
return f ? ~s + 1 : s;
}
template<typename T> inline void write(T x, const char *s = ""){
static int st[40]; int top = 0;
if(x < 0){putchar('-'); x = -x;}
if(!x) putchar('0');
while(x) st[++ top] = x % 10, x /= 10;
while(top) putchar(st[top --] + 48);
printf("%s", s);
}
template<typename T> inline void updmin(T &x, T y){if(x > y) x = y;}
template<typename T> inline void updmax(T &x, T y){if(x < y) x = y;}
template<typename T> inline void updadd(T &x, T y){(x += y % MOD) %= MOD;}
template<typename T> inline void updmul(T &x, T y){(x *= y % MOD) %= MOD;}
int cmp(DB a, DB b){if(fabs(a - b) < EPS) return 0; return a - b > EPS ? 1 : -1;}
}
using namespace _default;
const int N = 1e6 + 5;
int n, m, a[N], b[N], ans[N];
PII f[N][2];
signed main(){
n = read<int>(), m = n << 1;
uF(i, 1, m) a[i] = read<int>();
uF(i, 1, m) b[i] = read<int>();
f[1][0] = {1, 1}, f[1][1] = {0, 0};
uF(i, 2, m){
f[i][0] = f[i][1] = {INF, -INF};
if(a[i] >= a[i - 1]) updmin(f[i][0].X, f[i - 1][0].X), updmax(f[i][0].Y, f[i - 1][0].Y);
if(a[i] >= b[i - 1]) updmin(f[i][0].X, f[i - 1][1].X), updmax(f[i][0].Y, f[i - 1][1].Y);
if(b[i] >= a[i - 1]) updmin(f[i][1].X, f[i - 1][0].X), updmax(f[i][1].Y, f[i - 1][0].Y);
if(b[i] >= b[i - 1]) updmin(f[i][1].X, f[i - 1][1].X), updmax(f[i][1].Y, f[i - 1][1].Y);
++ f[i][0].X, ++ f[i][0].Y;
}
int cur = n, cs = INF;
dF(i, m, 1){
if(f[i][0].X <= cur && f[i][0].Y >= cur && a[i] <= cs) -- cur, cs = a[i];
else if(f[i][1].X <= cur && f[i][1].Y >= cur && b[i] <= cs) ans[i] = 1, cs = b[i];
else{
puts("-1");
return 0;
}
}
uF(i, 1, m) putchar(ans[i] ? 'B' : 'A');
puts("");
lovely _lzy_;
}