Gym 104855E Perfect Permutation

考虑最后对于每个 \(i\) 是选 \(a_i, b_i, c_i\) 之中哪一个的序列。
通过观察能发现序列去掉 \(b\) 后满足开头为 \(c\) 末尾为 \(a\) 这个序列就是合法的，同时整个序列都为 \(b\) 也是合法的。

首先如果是个合法序列，对于去掉 \(b\) 后的开头，其余不是 \(b\) 的下标肯定比其大，所以只能是 \(c\)，末尾只能是 \(a\) 同理。
然后对于去掉 \(b\) 后满足开头为 \(c\) 末尾为 \(a\) 的序列，考虑证明一定可以构造出对应的 \(p\)。
\(b\) 显然是简单的不考虑，只考虑 \(a, c\)。
把 \(a, c\) 的序列拆为多个满足前面都是 \(c\) 后面都是 \(a\) 的段，一个段一个段来处理。
首先令 \(p_i = i\)，接下来对于这个段内的下标循环右移 \(1\) 位，能发现变成了第一个为 \(c\) 其余的为 \(a\)，继续能发现循环右移了 \(x\) 位开头就有 \(x\) 个 \(c\)。
那只需根据开头的 \(c\) 的数量循环右移对应位数即可。

对于答案，就可以考虑 \(\text{DP}\)。
令 \(f_{i, 0 / 1}\) 为前 \(i\) 位是否出现了开头为 \(c\) 的最优值，\(g_{i, 0 / 1}\) 为考虑第 \(i\) 位及之后是否出现了末尾为 \(a\) 的最优值。
那么最后答案的选取就分为全选 \(b\) 或者前面为 \(c\) 后面为 \(a\) 拼起来，即 \(\max\{\sum\limits_{i = 1}^n b_i, \max\limits_{i = 1}^{n - 1} f_{i, 1} + g_{i + 1, 1}\}\)。
然后按照上面提到的方式构造即可。

时间复杂度 \(O(n)\)。

#include<bits/stdc++.h>
using i64 = long long;
const i64 inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 2e5 + 10;
int a[maxn], b[maxn], c[maxn];
i64 f[maxn][2]; int lf[maxn];
i64 g[maxn][2]; int lg[maxn];
int p[maxn], op[maxn];
inline void solve() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
    for (int i = 0; i <= n + 1; i++) for (int j : {0, 1}) f[i][j] = g[i][j] = -inf;
    f[0][0] = g[n + 1][0] = 0;
    for (int i = 1; i <= n; i++) {
        f[i][0] = f[i - 1][0] + b[i], f[i][1] = f[i - 1][0] + c[i], lf[i] = 0;
        i64 v = f[i - 1][1] + std::max({a[i], b[i], c[i]});
        if (v > f[i][1]) f[i][1] = v, lf[i] = 1;
    }
    for (int i = n; i; i--) {
        g[i][0] = g[i + 1][0] + b[i], g[i][1] = g[i + 1][0] + a[i], lg[i] = 0;
        i64 v = g[i + 1][1] + std::max({a[i], b[i], c[i]});
        if (v > g[i][1]) g[i][1] = v, lg[i] = 1;
    }
    i64 ans = 0; int w = 0;
    for (int i = 1; i <= n; i++) ans += b[i];
    for (int i = 1; i < n; i++) {
        i64 v = f[i][1] + g[i + 1][1];
        if (v > ans) ans = v, w = i;
    }
    for (int i = 1; i <= n; i++) p[i] = i;
    if (w) {
        for (int i = w, j = 1; i; i--) {
            if (! j) {op[i] = 0; continue;}
            if (! lf[i]) {j = 0, op[i] = 1; continue;}
            op[i] = a[i] >= std::max(b[i], c[i]) ? 2 : (b[i] >= std::max(a[i], c[i]) ? 0 : 1);
        }
        for (int i = w + 1, j = 1; i <= n; i++) {
            if (! j) {op[i] = 0; continue;}
            if (! lg[i]) {j = 0, op[i] = 2; continue;}
            op[i] = a[i] >= std::max(b[i], c[i]) ? 2 : (b[i] >= std::max(a[i], c[i]) ? 0 : 1);
        }
        for (int l = 1; l <= n; l++) {
            if (! op[l]) continue;
            std::vector<int> W;
            bool fl = 1; int cnt = 0;
            for (int r = l; r <= n && (fl || op[r] != 1); r++) {
                if (! op[r]) continue;
                W.push_back(r), op[r] == 1 ? (cnt++) : (fl = 0); 
            }
            for (int i = 0, j = W.size() - cnt; i < int(W.size()); i++, (++j) %= W.size()) p[W[i]] = W[j];
            for (int i : W) op[i] = 0;
        }
    }
    for (int i = 1; i <= n; i++) printf("%d ", p[i]); printf("\n");
}
int main() {
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}