题解：CF1144G Two Merged Sequences

· · 题解

给个诡异的贪心做法。

直接贪心或者 dp 不太好做，尝试寻找一些性质。观察这两个单调序列，整个原序列的最小值要么在单调增序列的开头，要么在单调减序列的末尾。

考虑最小值的位置在 p，如果让其在单调增序列的开头，[1,p) 的部分必然是单调减序列的开头部分。于是规约到一个子问题：对于区间 [p,n]，能否将其分为一个单调增序列和单调减序列，使得单调减序列中的最大值 <a_{p-1}。让最小值在单调减序列末尾的情况是类似的。

既然有了规约子问题的能力，考虑建出小根笛卡尔树，递归子问题判断：

由于每一步都是充分且必要的规约，所以正确性上是对的。时间复杂度是建树的 O(n)，常数略大。实现上要注意相同值的处理。

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using LL = long long;
constexpr int MAXN = 2e5 + 5;
int n, a[MAXN], L[MAXN], R[MAXN], lc[MAXN], rc[MAXN], mx[MAXN];
//[L[i], R[i]]: i 作为最小值的区间
bool up[MAXN], down[MAXN], ans[MAXN];
//up[u]: u 子树内部是否单调增，down[u]: u 子树内部是否单调减
void dfs(int u) {
    up[u] = down[u] = true, mx[u] = a[u];
    if (lc[u]) dfs(lc[u]), up[u] = false, down[u] &= down[lc[u]], mx[u] = max(mx[u], mx[lc[u]]);
    if (rc[u]) dfs(rc[u]), down[u] = false, up[u] &= up[rc[u]] && (a[u] < a[rc[u]]), mx[u] = max(mx[u], mx[rc[u]]);
}
bool check(int u, int l, int r) {
    bool p = down[lc[u]] && mx[lc[u]] <= l, q = up[rc[u]] && mx[rc[u]] <= r;
    if (p && q) {
        for (int i = L[u]; i < u; ++i) ans[i] = true;
        if (a[u] <= l) ans[u] = true;
        else if (a[u] > r) return false;
        return true;
    }
    if (p && a[u] <= r) {
        for (int i = L[u]; i < u; ++i) ans[i] = true;
        return check(rc[u], min(l, a[lc[u]] - 1), r);
    } else if (q && a[u] <= l) {
        ans[u] = true;
        return check(lc[u], l, min(r, a[rc[u]] - 1));
    }
    return false;
}
int main() {
    IOS;
    cin >> n;
    a[0] = a[n + 1] = -1e9;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        L[i] = i;
        while (L[i] > 1 && a[L[i] - 1] > a[i]) L[i] = L[L[i] - 1];
    }
    for (int i = n; i >= 1; --i) {
        R[i] = i;
        while (R[i] < n && a[R[i] + 1] >= a[i]) R[i] = R[R[i] + 1];
    }
    for (int i = 1; i <= n; ++i) {
        if (a[L[i] - 1] > a[R[i] + 1]) rc[L[i] - 1] = i;
        else lc[R[i] + 1] = i;
    }
    up[0] = down[0] = true;
    int rt = min_element(a + 1, a + 1 + n) - a;//以上是建树过程
    dfs(rt);
    a[0] = a[n + 1] = 2e5 + 1;
    bool res = check(rt, 2e5, 2e5);
    cout << (res ? "YES\n" : "NO\n");
    if (res) for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
    return 0;
}