题解：P17140 [NOI 2026] 线段

· · 题解

直接做。这样设状态可能舒服点。

区间图是弦图，没有环等价于没有三元环，也就是说每个坐标至多被覆盖 2 次，并且要求所有选中线段的并是连续区间。

先把线段按照左端点升序排序（相等时按照右端点升序排序），然后逐个加入，假设当前最大和次大的右端点分别为 R_1,R_2，现加入 [l,r]，那么需有 l\le R_1（连通）且 l>R_2（覆盖不超过 2 次）。

因此设 f_{k,x,i} 表示选了 k 条线段，最后选的是 [l_i,r_i]（显然 r_i 为 R_1,R_2 之一），另一个有效右端点为 x。能转移到的 i' 是一段连续区间，且新状态的 r'=\max(r_i,x)，转移时对行做差分即可，时间复杂度 \mathcal O(nmk)，用滚动数组，空间复杂度 \mathcal O(nm)。

注意为了避免算重，求出来合法 i' 的区间左端点要和 i+1 取 \max。

#include <bits/stdc++.h>
#include "segment.h"
using namespace std;
const int P = 998244353;
struct range { int l, r, i; };
inline void add(int &x, int y) { (x += y) >= P && (x -= P); }
void init(int c, int t) {}
vector<int> segment(int n, int m, int k, vector<int> l, vector<int> r) {
    vector<range> a;
    for (int i = 0; i < n; i++) a.push_back({l[i], r[i], i});
    sort(a.begin(), a.end(), [](const range &x, const range &y) { return x.l == y.l ? x.r < y.r : x.l < y.l; });
    vector<int> pt(m + 1, n);
    for (int i = 0; i <= m; i++) for (int j = i ? pt[i - 1] : 0; j < n; j++)
        if (a[j].l > i) { pt[i] = j; break; }
    vector<vector<int> > f(m + 1, vector<int>(n)), d(m + 1, vector<int>(n + 1));
    vector<int> ans(k + 1);
    fill(f[0].begin(), f[0].end(), 1), ans[1] = n;
    for (int s = 1; s < k; s++) {
        for (int i = 0; i <= m; i++) fill(d[i].begin(), d[i].end(), 0);
        for (int i = 0; i <= m; i++) for (int j = 0; j < n; j++) if (f[i][j]) {
            auto [mn, mx] = minmax(a[j].r, i);
            int l = max(pt[mn], j + 1), r = pt[mx] - 1;
            if (l <= r) add(d[mx][l], f[i][j]), add(d[mx][r + 1], P - f[i][j]);
        }
        for (int i = 0; i <= m; i++) for (int j = 0, c = 0; j < n; j++)
            add(c, d[i][j]), f[i][j] = c, add(ans[s + 1], c);
    }
    return ans;
}