题目链接：https://atcoder.jp/contests/agc061/tasks/agc061_c

做法

显然的方向：我们可以让一些选择非法，使得每个答案对应一个合法的选择。

准确来说，我们定义 $ff[i]$ 表示最大的 $j$ 使得 $i<k\le j$ 满足 $l_k<r_i$ 。

我们考虑每个顾客，填 $1$ 表示选择离开时候记录，$0$ 表示选择进入时记录。

那么一个位置填 $0$ 的条件为 $(i,ff[i]]$ 中有一个位置填 $0$ 或者存在一个位置 $k$ 填 $1$ 且 $i\in (k,ff[k]]$ 。

然后用 DP 维护合法方案即可。

一个显然的傻瓜式 DP 是：

$f_1[i]$ 表示 $i$ 填 $1$ 的目前合法序列个数。

$f_2[i]$ 表示 $i$ 填 $0$ 的可能合法序列个数。

$f_3[i]$ 表示 $i$ 填 $0$ ，$i-1$ 填 $1$ 的合法序列个数。

转移即可。

但是这里要讲一个优化，把 $f_3$ 优化掉，就是有一个转移是：

$f_2->f_3$ ，内容为往后放若干 $1$ 后放一个 $0$ ,那我们不妨先转移到 $f_1$ ，再减去没有放 $0$ 的序列（即减去不合法的序列）

于是：

$f_1[j]+=f2i),f_1[j]-=(j\in (i+1,ff[i]])$

但是这时又产生了一个疑惑，在化简了式子后可以缩减为：

$f_1[i+1]+=f_2[i],f_1[ff[i]]-=f_2[i]$ 。

其实不难发现，所有的不合法方案在 DP 过程中都一定会经过 $f_1[ff[i]]$ 且贡献为 $1$ ，减掉即可。

时间复杂度：$O(n)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<cstdio>
#include<cstring>
#define N 510000
using namespace std;
typedef long long LL;
const LL mod=998244353;
struct node{
    int l,r;
}a[N];int ff[N],n;
LL f1[N],f2[N],f3[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i].l,&a[i].r);
    int now=1;
    for(int i=1;i<=n;i++){
        while(now<n && a[now+1].l<=a[i].r)now++;
        ff[i]=now;
    }
    LL fnow=0;f1[1]=f2[1]=1;
    for(int i=1;i<=n;i++){
        (f1[i]+=fnow)%=mod;(f2[ff[i]+1]+=f1[i])%=mod;
        if(ff[i]>i)(f2[i+1]+=f2[i])%=mod,(f1[i+1]+=f2[i])%=mod,(f1[ff[i]]+=mod-f2[i])%=mod;
        (fnow+=f1[i])%=mod;(f3[ff[i]+1]+=f1[i])%=mod;
        (fnow+=mod-f3[i])%=mod;
    }
    // for(int i=1;i<=n;i++)printf("%d:%d %lld %lld\n",i,ff[i],f1[i],f2[i]);
    printf("%lld\n",fnow);
    return 0;
}