线段

Mier_Samuelle · 2026-07-25 14:18:10 · 题解

树 = 连通 + 无环。连通意味着必须与前面选的线段相交，无环意味着只能与一条线段相交。发现这个条件只与已选线段中次大和最大的右端点有关，据此，定义 f_{i,j,x,y}，表示考虑前 i 条线段，已经选了 j 条，次大和最大的右端点分别为 x,y，转移分三类：

1. 不选 i，则 f_{i,j,x,y} \leftarrow f_{i-1,j,x,y}。
2. 选 i，且 x<l_i \le y \le r_i，则 f_{i,j,y,r_i} \leftarrow f_{i-1,j-1,x,y}。
3. 选 i，且 x<l_i \le r_i < y，则 f_{i,j,r_i,y} \leftarrow f_{i-1,j-1,x,y}。

转移前将线段按左端点排序。第一维可简单地滚掉，空间 O(m^2k)，时间 O(nm^2k)，可以获得 20 分。

进一步地，发现转移的条件已经决定了线段是按左端点升序选择的，故可以不要 i 这一维，将 j 提到第一维，滚掉它。暴力处理前两条线段。空间 O(m^2)，时间 O(nm^2k)，可以获得 40 分。

最后，发现转移就是对 x 这一维求前缀和，可简单地优化成 O(1)。至此，空间 O(m^2)，时间 O(nmk)，可以通过。

:::success[Code]{open}

#include "segment.h"
#include <vector>
#include <algorithm>
#include <cstring>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 3010, MAXM = 1010;
const int MOD = 998244353;
int f[MAXM][MAXM], g[MAXM][MAXM], pre[MAXM][MAXM];
pii a[MAXN];
void add(int &x, int y){
    x += y;
    if (x >= MOD){
        x -= MOD;
    }
    return;
}
void init(int c, int t){
    return;
}
std::vector<int> segment(int n, int m, int k, std::vector<int> l_vec, std::vector<int> r_vec){
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    memset(pre, 0, sizeof(pre));
    for (int i = 1; i <= n; i++){
        a[i].fi = l_vec[i - 1];
        a[i].se = r_vec[i - 1];
    }
    std::vector<int> res(k + 1, 0);
    for (int i = 1; i <= k; i++){
        for (int x = 0; x <= m; x++){
            for (int y = x; y <= m; y++){
                g[x][y] = f[x][y];
                f[x][y] = 0;
            }
        }
        if (i == 1){
            for (int p = 1; p <= n; p++){
                int r = a[p].se;
                add(f[0][r], 1);
            }
        }
        else if (i == 2){
            for (int p = 1; p <= n; p++){
                for (int q = p + 1; q <= n; q++){
                    if (min(a[p].se, a[q].se) >= max(a[p].fi, a[q].fi)){
                        int x = min(a[p].se, a[q].se);
                        int y = max(a[p].se, a[q].se);
                        add(f[x][y], 1);
                    }
                }
            }
        }
        else{
            for (int y = 1; y <= m; y++){
                pre[0][y] = 0;
                for (int x = 1; x <= y; x++){
                    pre[x][y] = (pre[x - 1][y] + g[x][y]) % MOD;
                }
            }
            for (int p = 1; p <= n; p++){
                int l = a[p].fi, r = a[p].se;
                for (int y = l; y <= m; y++){
                    if (y <= r){
                        add(f[y][r], pre[l - 1][y]);
                    }
                    else{
                        add(f[r][y], pre[l - 1][y]);
                    }
                }
            }
        }
        int ans = 0;
        for (int x = 0; x <= m; x++){
            for (int y = x; y <= m; y++){
                add(ans, f[x][y]);
            }
        }
        res[i] = ans;
    }
    return res;
}

:::