题目链接
题目解法
易知总情况数为 \(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;
}