题解：AT_agc079_b [AGC079B] Range Record

P2441M · 2026-11-10 21:27:04 · 题解

我是大区。

设 h_i 表示 p[i..n] 的前缀最大值个数，把区间前缀最大值个数转化为 h_l-\min\limits_{l\leq i\leq r}h_i+1。设 a_{l,r}=\min\limits_{l\leq i\leq r}h_i，则限制变成 a_{l_j,l_j}-a_{l_j,r_j}=c_j-1。

观察 a 的其他限制：

把限制全部写成 \geq 的形式：

把所有 a_{l,r} 视作变量，初始时全部赋为 1。用队列维护所有变量，每次取出一个变量时，用这个变量更新其他变量的下界，若某次更新后 a_{i,i}>n+1-i 则判无解。否则最终我们就可以得到一组合法的 h。得到一组合法的 h 后，按 (h_i,i) 从小到大考虑每个位置，从大到小填值即可。

每个变量最多出队 \mathcal{O}(n) 次，时间复杂度 \mathcal{O}(n^3)。

:::success[代码]

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using i128 = __int128;
using ui = unsigned int;
using ull = unsigned long long;
using u128 = unsigned __int128;
using ld = long double;
using pii = pair<int, int>;
const int MAXN = 105;

template<typename T> T lowbit(T x) { return x & -x; }
template<typename T> void chkMin(T &x, T y) { x = y < x ? y : x; }
template<typename T> void chkMax(T &x, T y) { x = x < y ? y : x; }
constexpr int lg2(ll x) { return 63 ^ __builtin_clzll(x); }
constexpr ll bitCeil(ll x) { return x == 1 ? 1ll : 1ll << lg2(x - 1) + 1; }

int tc, n, m, ord[MAXN], p[MAXN], c[MAXN][MAXN], a[MAXN][MAXN];
bool vis[MAXN][MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> tc;
    while (tc--) {
        cin >> n >> m;

        queue<pii> Q;
        for (int l = 1; l <= n; ++l) {
            for (int r = l; r <= n; ++r) {
                c[l][r] = -1;
                a[l][r] = 1;
                vis[l][r] = true;
                Q.emplace(l, r);
            }
        }

        for (int i = 1; i <= m; ++i) {
            int l, r, x;
            cin >> l >> r >> x;
            c[l][r] = x - 1;
        }

        bool ok = true;

        auto upd = [&](int l, int r, int x) {
            if (!ok || a[l][r] >= x) return;
            if (x > n - r + 1) {
                ok = false;
                return;
            }
            a[l][r] = x;
            if (!vis[l][r]) {
                vis[l][r] = true;
                Q.emplace(l, r);
            }
        };

        while (!Q.empty() && ok) {
            auto [l, r] = Q.front();
            Q.pop();
            vis[l][r] = false;

            int x = a[l][r];
            if (l == r) {
                if (l < n) upd(l + 1, l + 1, x - 1);
                for (int nr = l + 1; nr <= n; ++nr) {
                    if (c[l][nr] != -1) upd(l, nr, x - c[l][nr]);
                }
            } else {
                if (c[l][r] != -1) upd(l, l, x + c[l][r]);
                upd(l, r - 1, x);
                upd(l + 1, r, x);
            }

            if (r < n) upd(l, r + 1, min(a[l][r], a[l + 1][r + 1]));
            if (l > 1) upd(l - 1, r, min(a[l][r], a[l - 1][r - 1]));
        }

        if (!ok) {
            cout << "No\n";
            continue;
        }

        cout << "Yes\n";
        iota(ord + 1, ord + n + 1, 1);
        sort(ord + 1, ord + n + 1, [&](int x, int y) {
            return a[x][x] != a[y][y] ? a[x][x] < a[y][y] : x < y;
        });
        for (int i = 1; i <= n; ++i) p[ord[i]] = n + 1 - i;
        for (int i = 1; i <= n; ++i) cout << p[i] << " \n"[i == n];
    }

    return 0;
}

:::