CF 2066F Curse

rizynvu · 2025-07-12 20:03:13 · 题解

cnblogs。

这也太难了，成官方题解复读机了/ll。

首先考虑一个例子：a = [-1, -1]。

那么接下来的操作一定是选择一个 -1 进行替换，接下来分讨替换的数组的最大子段和：

• 若 > -1，则接下来只能替换这个数组中的最大子段和的位置。
• 若 = -1，则接下来可以替换这个数组中的最大子段和的位置，也可以替换 -1。注意这个时候如果一个连续段既包含了左边的一部分又包含了 -1 则其和一定 < -1，所以这是不可能的。
• 若 < -1，则接下来只能替换右边的 -1。

于是能够发现，我们可以增加一个分界符：[-1, |, -1]，其中每一步替换一定不会跨过分界符。

那么接下来就是要尝试去划分分界符了。
首先考虑找到最大子段和的段 [l_i, r_i](1\le i\le m)，此时称第 i 段是有用的当且仅当不存在 1\le j\le m, j\not = i 满足 [l_j, r_j]\subseteq [l_i, r_i]，然后只保留下这些有用的段，对于中间的一些没有分进段内的元素继续递归下去分段。

这是因为若 [l_j, r_j]\subseteq [l_i, r_i]，那么把 [l_j, r_j] 替换成任意的数组 a' 都可以通过把 [l_i, r_i] 替换成 [l_i, l_j) + a' + (r_j, r_i]（这里的 + 指拼接）来实现。

因为有用的段不交，所以这个划分一定可以进行。
证明：考虑若 [l_i, r_i]\cap [l_j, r_j]\not = \varnothing 且互不包含，不妨令 l_i < l_j，那么有 sum(l_i, r_j) + sum(l_j, r_i) = sum(l_i, r_i) + sum(l_j, r_j)，所以一定可以尝试替换为更大的 sum 的区间或者替换为长度更长的 [l_i, r_j]。

实现时可以直接考虑找出给定范围 [l, r] 中和最大且长度最长的区间， 然后往两侧递归。

于是此时其实就已经知道了所有分界线，也就可以划分出许多个段 [l_i, r_i](1\le i\le m)（这里的名字跟上面的重了，但是因为上面的定义都不会用到了就这样吧）。
这些划分出来的段一定满足，对于这个段内的第一次替换操作一定是把整个段替换段。

紧接着，我们可以说明，进行的替换操作一定形如这样：

• 选择一个值 x，也就是主动划分了一个分界线。
• 对于所有 sum(l_i, r_i) < x 的段全部保留。
• 对于 sum(l_i, r_i)\ge x 的段均可以进行替换，但是要保证至多一个段替换后最大子段和 > x。

如果合法，那么这个过程是一定可以构造的，考虑先把所有 sum(l_i, r_i)\ge x 的段都直接替换为 [x]（即 x 一个元素），然后先处理 sum(l_i, r_i)\le x 的段，最后处理 sum(l_i, r_i) > x 的段。

且这样其实也说明了每一段至多也只会替换一次。

于是可以外层枚举 x，内层设计一个 dp。

设 f_{i, j, 0 / 1} 表示目前在区间顺序（l_i 升序）的第 i 个区间，目前在匹配 b 数组的第 j 个位置，此时是否有选择最大子段和 > x 的段是否可行。

转移考虑进行分讨：

• 若 sum(l_i, r_i) < x，则无法匹配，直接枚举每个 j 然后尝试接下来的 r_i - l_i + 1 个元素，复杂度是 \mathcal{O}(\sum\limits_{i} (r_i - l_i + 1)m) = \mathcal{O}(nm) 的。

• 若 sum(l_i, r_i)\ge x，则继续分讨接下来是选择替换成什么样的段：

  • 若选择替换成最大子段和 > x 的段，那么这一段可以匹配上 j 为左端点的任意一个区间，即 f_{i + 1, k + 1, 1}(j\le k\le m)。
  • 若选择替换成最大子段和 \le x 的段，考虑找到最大的 k 满足 b 中 [j, k] 最大子段和 \le x，那么就可以替换为左端点为 j 右端点 \le k 的任意区间，即 f_{i + 1, h + 1, *}(j\le h\le k)。

  若直接转移复杂度是 \mathcal{O}(nm^2) 的。

  但是考虑到此时只关心合法性，若一个位置已经为 1 显然不需要重复赋值。
  所以对于第一类，肯定只需要找到最小的 j 满足 f_{i, j, 0} 合法即可，复杂度为 \mathcal{O}(nm)。
  对于第二类，首先 k 可以通过双指针解决，对于转移可以维护一个指针 r_{0 / 1} 表示 \le r_{o} 的类型为 o 的右端点都不需要考虑了，均摊可以知道复杂度也为 \mathcal{O}(nm)。

于是求解合法性的过程都可以在 \mathcal{O}(nm^2) 的复杂度内做完。

对于构造，其实刚刚 dp 的过程就已经给出了对应的步骤，记录下来按照上文所述的构造方法构造即可。

我划分段时写的很暴力，复杂度是 \mathcal{O}(n^3 + nm^2) 的。

代码也基本是参考的 std/ll。

#include <bits/stdc++.h>

constexpr int inf = 1e9;

constexpr int maxn = 500 + 5;

int n, a[maxn], suma[maxn];
int m, b[maxn], sumb[maxn];

std::vector<std::vector<int>> par;
std::vector<int> parsum;

void split(int l, int r) {
    if (l > r) return ;

    std::array<int, 4> mx = {-inf, 0, 0, 0};
    for (int i = l; i <= r; i++) {
        for (int j = i; j <= r; j++) {
            mx = std::max(mx, {suma[j] - suma[i - 1], j - i + 1, i, j});
        }
    }

    split(l, mx[2] - 1);
    par.push_back({});
    for (int i = mx[2]; i <= mx[3]; i++) {
        par.back().push_back(a[i]);
    }
    parsum.push_back(mx[0]);
    split(mx[3] + 1, r);
}

int mxb[maxn][maxn];

std::vector<std::tuple<int, int, std::vector<int>>> ans;

bool dp[maxn][maxn][2];
std::array<int, 2> lst[maxn][maxn][2];

inline bool check(int bound) {
    for (int i = 0; i <= par.size(); i++) {
        memset(dp[i], 0, sizeof(dp[i]));
    }
    dp[0][1][0] = true;

    for (int i = 0; i < par.size(); i++) {
        if (par[i] != std::vector<int>{inf}) {
            for (int j = 1; j + par[i].size() - 1 <= m; j++) {
                bool ok = true;
                for (int k = 0; ok && k < par[i].size(); k++) {
                    ok &= par[i][k] == b[j + k];
                }

                if (! ok) continue;
                for (int o : {0, 1}) {
                    if (dp[i][j][o]) {
                        dp[i + 1][j + par[i].size()][o] = true;
                        lst[i + 1][j + par[i].size()][o] = {j, o};
                    }
                }
            }
            continue;
        }

        int lstk[2] = {0, 0};
        for (int j = 1, r = 1; j <= m; j++) {
            if (r < j) r++;
            while (r <= m && mxb[j][r] <= bound) r++;

            if (! lstk[0] && dp[i][j][0]) {
                for (int k = j; k <= m; k++) {
                    dp[i + 1][k + 1][1] = true;
                    lst[i + 1][k + 1][1] = {j, 0};
                }
            }

            for (int o : {0, 1}) {
                if (dp[i][j][o]) {
                    lstk[o] = std::max(lstk[o], j);
                    while (lstk[o] < r) {
                        dp[i + 1][lstk[o] + 1][o] = true;
                        lst[i + 1][lstk[o] + 1][o] = {j, o};
                        lstk[o]++;
                    }
                }
            }
        }
    }

    if (! dp[par.size()][m + 1][1]) return false;

    int ci = -1, cl = -1, cr = -1;
    for (int i = par.size(), j = m + 1, o = 1; i > 0; i--) {
        auto [lstj, lsto] = lst[i][j][o];
        if (par[i - 1] == std::vector<int>{inf}) {
            if (o == lsto) {
                int id = 0;
                for (int k = 0; k < i - 1; k++) id += par[k].size();
                std::vector<int> now;
                for (int k = lstj; k < j; k++) now.push_back(b[k]);
                ans.emplace_back(id, id + par[i - 1].size() - 1, now);
                par[i - 1] = now;
            } else {
                ci = i - 1, cl = lstj, cr = j - 1;
            }
        }
        j = lstj, o = lsto;
    }

    int id = 0;
    for (int j = 0; j < ci; j++) id += par[j].size();
    std::vector<int> now;
    for (int j = cl; j <= cr; j++) now.push_back(b[j]);
    ans.emplace_back(id, id + par[ci].size() - 1, now);
    par[ci] = now;

    return true;
}

inline void solve() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= m; i++) scanf("%d", &b[i]);

    for (int i = 1; i <= n; i++) suma[i] = suma[i - 1] + a[i];
    for (int i = 1; i <= m; i++) sumb[i] = sumb[i - 1] + b[i];

    par.clear(), parsum.clear();
    split(1, n);

    for (int i = 1; i <= m; i++) mxb[i][i] = b[i];
    for (int l = m; l >= 1; l--) {
        for (int r = l + 1; r <= m; r++) {
            mxb[l][r] = std::max({mxb[l + 1][r], mxb[l][r - 1], sumb[r] - sumb[l - 1]});
        }
    }

    std::vector<int> order(par.size());
    std::iota(order.begin(), order.end(), 0);
    std::sort(order.begin(), order.end(), [&](int x, int y) {
        return parsum[x] > parsum[y];
    });

    ans.clear();
    for (int p = 0; p < order.size(); p++) {
        const int i = order[p];
        const int bound = parsum[i];

        int id = 0;
        for (int j = 0; j < i; j++) id += par[j].size();
        ans.emplace_back(id, id + par[i].size() - 1, std::vector<int>{inf});
        par[i] = {inf};

        if (p + 1 < order.size() && parsum[order[p + 1]] == bound) continue;

        if (check(bound)) {
            printf("%zu\n", ans.size());
            for (auto [l, r, vec] : ans) {
                printf("%d %d %zu\n", l + 1, r + 1, vec.size());
                for (int x : vec) printf("%d ", x == inf ? bound : x);
                puts("");
            }
            return puts(""), void();
        }
    }
    printf("-1\n\n");
}

int main() {
    int t; scanf("%d", &t);
    while (t--) solve();
    return 0;
}