题解 CF1620F 【Bipartite Array】

· · 题解

这题显然答案很多，比如样例第三组数据也可以是 -4,1,-3,2、-4,1,-3,-2 等等。

那么显然这题需要 spj，考虑他的 spj 是咋写的。发现好像没有那么好写：图的边数可以达到 10^{12} 量级，而且不太好优化建图，可能需要一个主席树。但是主席树跑 10^6 时空压力都很大，同时这是 CF 题，万一这题 hack 巨大多，评测机就直接寄了。

这实际上提示我们可能存在一个 bipartite array 的不直接的判定方式，考虑这个判定方式是什么。

考虑这个图，它可以被分成两个点集，点集之间没有边。回到序列，一个序列对应一个空图，显然这个序列必须递增。

所以一个 bipartite array 必然可以被拆成两个上升子序列。

但是这题可以把元素改成负的。考虑到每一个子序列肯定都是它的一段前缀被改成负的，那么肯定原始序列上这个前缀需要递减。

所以这个问题实际上是要求我们把原始序列拆成两个单谷子序列。

然后就是套路前缀 DP。因为我们只关心拆出来的子序列的最后一个元素，同时两个最后一个元素中必然有一个肯定是整个序列的最后一个元素，所以设 f_{i,j,k} 表示前 i 个元素，包含第 i 个元素的子序列当前在上升/下降（对应 j 取 0/1），不包含第 i 个元素的子序列当前在上升/下降（对应 k 取 0/1），不包含第 i 个元素的子序列的最后一个元素最大/最小是什么。其中当 k=0 时找最大的来给递减留出尽量大空间，k=1 时找最小的来给递增留出尽量大空间。

然后就是暴力分类讨论转移，考虑每一个状态下新的元素接到哪个子序列后面以及改变递增/递减状态就可以了。具体过程较简单，不赘述。

最后是输出方案，记三个值，分别表示转移点的 j,k（i 一定是当前状态的 i 减去 1），以及最后一个数是否与上一个数在同一个子序列里面。可以压成一个 0\sim 7 中的整数来存储。从 n,1,1 反着搜一遍就可以得到两个单谷子序列，分别把前面递减的部分反过去就可以了。

于是这题就做完了，复杂度 O(n)。

#include <bits/stdc++.h>
using namespace std;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int qread() {
    register char c = getchar();
    register int x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + c - 48;
        c = getchar();
    }
    return x * f;
}

const int N = 1000005;
int n, f[N][2][2], path[N][2][2], a[N], ans[N];

inline void Read() {
    n = qread();
    for (int i = 1;i <= n;i++) a[i] = qread();
}

inline void UpdMax(int i, int j, int k, int val, int pth) {
    if (val > f[i][j][k]) {
        f[i][j][k] = val;
        path[i][j][k] = pth;
    }
}

inline void UpdMin(int i, int j, int k, int val, int pth) {
    if (val < f[i][j][k]) {
        f[i][j][k] = val;
        path[i][j][k] = pth;
    }
}

inline void Solve() {
    f[1][0][0] = 0x3f3f3f3f;
    f[1][1][0] = 0x3f3f3f3f;
    f[1][0][1] = 0xf3f3f3f3;
    f[1][1][1] = 0xf3f3f3f3;
    for (int i = 2;i <= n;i++) {
        f[i][0][0] = f[i][1][0] = 0xf3f3f3f3;
        f[i][0][1] = f[i][1][1] = 0x3f3f3f3f;
    }
    for (int i = 2;i <= n;i++) {
        if (f[i - 1][0][0] >= 1) {
            if (a[i] < a[i - 1]) UpdMax(i, 0, 0, f[i - 1][0][0], 0);
            UpdMax(i, 1, 0, f[i - 1][0][0], 0);
            if (a[i] < f[i - 1][0][0]) UpdMax(i, 0, 0, a[i - 1], 1);
            UpdMax(i, 1, 0, a[i - 1], 1);
        }
        if (f[i - 1][1][0] >= 1) {
            if (a[i - 1] < a[i]) UpdMax(i, 1, 0, f[i - 1][1][0], 4);
            if (f[i - 1][1][0] > a[i]) UpdMin(i, 0, 1, a[i - 1], 5);
            UpdMin(i, 1, 1, a[i - 1], 5);
        }
        if (f[i - 1][0][1] <= n) {
            if (a[i - 1] > a[i]) UpdMin(i, 0, 1, f[i - 1][0][1], 2);
            UpdMin(i, 1, 1, f[i - 1][0][1], 2);
            if (f[i - 1][0][1] < a[i]) UpdMax(i, 1, 0, a[i - 1], 3);
        }
        if (f[i - 1][1][1] <= n) {
            if (a[i - 1] < a[i]) UpdMin(i, 1, 1, f[i - 1][1][1], 6);
            if (f[i - 1][1][1] < a[i]) UpdMin(i, 1, 1, a[i - 1], 7);
        }
    }
    if (f[n][1][1] > n) cout << "NO\n";
    else {
        cout << "YES\n";
        vector <int> seq[2];
        int j = 1, k = 1, cur = 0;
        for (int i = n;i >= 1;i--) {
            ans[i] = a[i];
            int nxt = path[i][j][k];
            seq[cur].push_back(i);
            cur ^= (nxt & 1);
            j = (nxt >> 2) & 1;
            k = (nxt >> 1) & 1;
        }
        for (int k = 0;k < 2;k++) {
            reverse(seq[k].begin(), seq[k].end());
            int siz = seq[k].size();
            for (int i = 0;i < siz - 1;i++) {
                if (a[seq[k][i]] > a[seq[k][i + 1]]) ans[seq[k][i]] = -ans[seq[k][i]];
                else break;
            }
        }
        for (int i = 1;i <= n;i++) cout << ans[i] << " ";
        cout << '\n';
    }
}

int main() {
    std::ios::sync_with_stdio(0);
    int t = qread();
    while (t--) {
        Read();
        Solve();
    }
    cout.flush();
    #ifdef CFA_44
    while (1);
    #endif
    return 0;
}