题解：P10807 [LMXOI Round 2] Disaster

Li00000 · 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;
}