526互联

P6891 [JOISC2020] ビルの飾り付け 4

发布时间 2023-07-05 13:34:54作者: 牛肉爱吃dks

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