P17140 [NOI 2026] 线段 题解

题目链接：P17140 [NOI 2026] 线段

简单题，为什么没做出来呢？

首先观察可得最终形成的树一定是一条链挂着若干个单点，将链和菊花分别 dp 出来再拼起来显然很没前途（至少会 MLE，为什么我会执着于这个思路 2h 呢？），发现如果我们从左到右加入链上的点，对于链上的每个点挂的单点也是从左到右增加，则最大和次大的 $ r $ 一定单调不减，而且每次转移两个中一定有一个会增加，那么直接 dp 即可，$ k $ 这一维滚动掉，然后做一下前缀和就可以优化成 $ O(nmk) $。

代码：

#include<bits/stdc++.h>
#include"segment.h"
using namespace std;
const int mod=998244353;
struct node{int l,r;
}a[3005];
int dp[1005][1005],sdp[1005][1005];
int add(int x,int y)
{return (x+y>=mod?x+y-mod:x+y);
}
int divd(int x,int y)
{return (x<y?x-y+mod:x-y);
}
void init(int c,int t)
{return ;
}
vector<int> segment(int n,int m,int K,vector<int> l,vector<int> r)
{for(int i=0;i<n;i++){a[i+1].l=l[i];a[i+1].r=r[i];}memset(dp,0,sizeof(dp));vector<int> ans(K+1,0);for(int k=1;k<=K;k++){for(int i=1;i<=m;i++){for(int j=0;j<=m;j++){dp[i][j]=0;}}if(k==1){for(int id=1;id<=n;id++){dp[a[id].r][0]++;}for(int i=1;i<=m;i++){for(int j=0;j<=i;j++){sdp[i][j]=add((j?sdp[i][j-1]:0),dp[i][j]);}}}else if(k==2){for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if(max(a[i].l,a[j].l)<=min(a[i].r,a[j].r)){dp[max(a[i].r,a[j].r)][min(a[i].r,a[j].r)]++;}}}for(int i=1;i<=m;i++){sdp[i][0]=dp[i][0];for(int j=1;j<=i;j++){sdp[i][j]=add(sdp[i][j-1],dp[i][j]);}}}else{for(int i=1;i<=m;i++){for(int id=1;id<=n;id++){int j=a[id].r,ql=a[id].l;if(ql>i)continue;if(i<j){dp[j][i]=add(dp[j][i],sdp[i][ql-1]);}else{dp[i][j]=add(dp[i][j],sdp[i][ql-1]);}}}for(int i=1;i<=m;i++){sdp[i][0]=dp[i][0];for(int j=1;j<=i;j++){sdp[i][j]=add(sdp[i][j-1],dp[i][j]);}}}for(int i=1;i<=m;i++){for(int j=0;j<=i;j++){ans[k]=add(ans[k],dp[i][j]);}}}return ans;
}