Solution-P17140

· · 题解

以下称题目中的 k 为 p，线段的下标从 1 开始。

树实际上是满足以下两个条件的图：

首先将线段按 l 升序排序，接下来的线段 i 指排序后的第 i 条线段。

将线段 1\sim n 依次尝试加入先前的优美集合中。不难发现我们只关心集合中线段次大和最大的 r，记次大的 r 为 x，最大的 r 为 y。那么只有满足 x<l_i\le y 的优美集合加入线段 i 后仍为优美集合。前者是要求不存在 \ge3 条线段交于一点（否则就成环了），后者是要求线段 i 与前面的线段有交（否则就不连通了）。

考虑设 f_{k,i,x,y} 表示选了 k 条线段，l 最大的线段为线段 i，次大的 r 为 x，最大的 r 为 y 时的方案数。

这个东西看着就很大坨，尝试优化。不难发现 x,y 中一定有一个是 r_i，否则因为 l_i 是最大的，r_i 至少是第 3 大，所以会有 \ge3 条线段交于一点，不符合条件。于是可以记 f_{k,i,a} 表示选了 k 条线段，l 最大的线段为线段 i，次大的 r 为 \min\{r_i,a\}，最大的 r 为 \max\{r_i,a\} 时的方案数。

考虑 f_{k,i,a} 能怎么转移，首先枚举下一根线段 j(j>i)，显然 j 还需要满足 \min\{r_i,a\}<l_j\le\max\{r_i,a\}。上面我们说了，加入线段 j 后 r_j 一定是最大或次大的 r，那么意味着 \min\{r_i,a\} 此时变成第 3 大，于是我们令 f_{k+1,j,\max\{r_i,a\}}\gets f_{k+1,j,\max\{r_i,a\}}+f_{k,i,a}。

至此时间复杂度已经为 O(n^2mp) 了，利用滚动数组可以做到空间复杂度 O(nm)。发现转移时的 j 是连续的，且第三维是固定的，考虑直接对于每个 b\in[1,m]，求出最大的满足 l_j\le b 的 j，记为 u_b。然后差分处理第二维的区间加，转成单点修改，最后再对第二维做前缀和即可。

需要特别注意从 k=1 向 k=2 的转移。

时间复杂度 O(nmp)，代码很好写：

#include"segment.h"
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
struct node{
    int l,r;
    inline friend bool operator < (node i,node j){
        return i.l<j.l;
    }
    inline friend bool operator < (int i,node j){
        return j.l>i;
    }
}x[3001];
int f[2][3001][1001],s,u[1001];
vector<int>g;
inline void add(int& i,int w){
    i=i+w>=mod?i+w-mod:i+w;
}
inline void sub(int& i,int w){
    i=i-w<0?i-w+mod:i-w;
}
void init(int c,int t){
    return;
}
vector<int>segment(int n,int m,int p,vector<int>l,vector<int>r){
    g.clear();
    g.push_back(0);
    for(int i=1;i<=n;i++){
        x[i].l=l[i-1];
        x[i].r=r[i-1];
    }
    sort(x+1,x+n+1);
    for(int i=1;i<=n;i++){
        for(int a=1;a<=m;a++){
            f[0][i][a]=0;
        }
    }
    for(int a=1;a<=m;a++){
        u[a]=upper_bound(x+1,x+n+1,a)-x-1;
    }
    for(int i=1;i<=n;i++){
        sub(f[0][i][x[i].r],1);
        add(f[0][u[x[i].r]][x[i].r],1);
    }
    g.emplace_back(n);
    for(int k=2;k<=p;k++){
        for(int i=1;i<=n;i++){
            for(int a=1;a<=m;a++){
                f[k&1^1][i][a]=0;
            }
        }
        for(int i=n-1;i>=1;i--){
            for(int a=1;a<=m;a++){
                add(f[k&1][i][a],f[k&1][i+1][a]);
            }
        }
        s=0;
        for(int i=1;i<=n;i++){
            for(int a=1;a<=m;a++){
                add(s,f[k&1][i][a]);
            }
        }
        g.emplace_back(s);
        if(k==p){
            break;
        }
        for(int i=1;i<=n;i++){
            for(int a=1;a<=m;a++){
                sub(f[k&1^1][max(i,u[min(x[i].r,a)])][max(x[i].r,a)],f[k&1][i][a]);
                add(f[k&1^1][u[max(x[i].r,a)]][max(x[i].r,a)],f[k&1][i][a]);
            }
        }
    }
    return g;
}