自动搬运

查看原文

来自洛谷，原作者为

	Li00000 .

搬运于2025-08-24 23:01:28，当前版本为作者最后更新于2024-05-08 20:29:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑 dp，记 $f_i$ 表示以 $i$ 结尾的方案数，枚举右端点 $R$，找到所有合法区间 $[L,R]$，有转移：

考虑题目限制的影响：

• 当 $R<i$ 时，对 $L$ 没有影响。

• 当 $i\le R< r_i$ 时，要求 $L>l_i$。

• 当 $r_i\le R$ 时，要求 $L>i$。

对于每个右端点 $R$，可转移的 $L$ 是以 $R$ 为右端点的一段区间，所以对影响取 $\max$ 找到所有可转移的 $L$，用前缀和优化 dp 转移即可。

时间复杂度 $O(N)$。

Code

#include<bits/stdc++.h>
#define N 2000005
using namespace std;
int n;
int f[N],sum[N];
int mx[N];
int p=1;
const int mod=998244353;
inline int read(){
    int x=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x;
}
inline int Max(int x,int y){return (x>y)?x:y;}
inline int M(long long x){return (x<mod)?x:x-mod;}
int main(){
    n=read();
    for(int i=1,l,r;i<=n;++i){
        l=read();r=read();
        mx[r]=Max(mx[r],i+1);
        mx[i]=Max(mx[i],l+1);
    }
    f[0]=sum[0]=1;
    for(int i=1;i<=n;++i){
        p=Max(p,mx[i]);
        f[i]=sum[i-1];
        if(p-2>=0) f[i]=M(M(1ll*f[i]-sum[p-2]+mod));
        sum[i]=M(1ll*sum[i-1]+f[i]);
    }
    printf("%d",f[n]);
    return 0;
}