[AGC061C] First Come First Serve 题解

题目链接

点击打开链接

题目解法

易知总情况数为 \(2^n\)
考虑重复计算的情况为：存在 \([l_i,r_i]\)，满足没有 \([l_j,r_j](i\neq j)\) 选在此区间中

可以得到一个容斥的 \(dp\) 做法
这个转移虽然感觉很显然，但卡了我一个晚上，一直调不出
令 \(f_i\) 为到 \(i\) 的容斥情况下的权值和
首先需要忽略满足 \(l_j<r_k,l_i<r_j(k<j<i)\) 的区间 \([l_k,r_k]\)，这一步是很关键的，理由也比较显然
其他的可以直接预处理 \(p_i\) 表示满足 \(l_j<r_i\) 的最大的 \(j\)，然后前缀和预处理一下不难做，具体可以去看其他题解，这里不细说

这道题的关键在于想到容斥以及后面的忽略一些不需要的区间

时间复杂度 \(O(n)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=500100,P=998244353,iv2=499122177;
int f[N],s[N];
int l[N],r[N],p[N];
int pw2[N],ipw2[N];
int qmi(int a,int b){
    int res=1;
    for(;b;b>>=1){
        if(b&1) res=1ll*res*a%P;
        a=1ll*a*a%P;
    }
    return res;
}
int main(){
    int n=read();
    pw2[0]=1;
    F(i,1,n+1) pw2[i]=pw2[i-1]*2%P;
    ipw2[0]=1;
    F(i,1,n+1) ipw2[i]=1ll*ipw2[i-1]*iv2%P;
    F(i,1,n) l[i]=read(),r[i]=read();
    l[n+1]=r[n+1]=1e9;
    int j=0;
    F(i,1,n){
        while(j<n&&l[j+1]<r[i]) j++;
        p[i]=j;
    }
    j=0;f[0]=1,s[0]=iv2;
    int k=0;
    F(i,1,n+1){
        while(r[k]<l[i]) k++;
        while(j<n&&p[j+1]<=k-1) j++;
        f[i]=P-1ll*s[j]*pw2[k]%P;
        s[i]=(s[i-1]+1ll*f[i]*ipw2[p[i]+1])%P;
    }
    printf("%d\n",(P-f[n+1])%P);
    fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}