题目大意

给定n个区间[L_i, R_i]，每个区间有 1/2 的概率被选择，表示第i个被选择的线段，求图片说明的期望，答案对998244353取模。

解题思路

不同于官方题解通过树形dp的思路，我们的方法是通过累加每种情况对期望的贡献来求解。
线段的交取决于最大的左端点以及最小的右端点，同时维护两个东西比较困难。

当然，我们先添加上最左最优的端点，处理所有线段都不选择的情况；
再按照线段左端点从大到小排序，那么排序后的线段的交，就取决于最小的右端点，以及第一个被选择的线段的左端点，再在离散化后构建好一棵线段树，再映射到原值。
先明确，我们要的

接下来要进行的操作是：

  • 简单易得，遍历区间[i,i+1]，维护包含该区间的线段的交集的期望，通过计算所有区间的贡献和得到。从m个线段找出a个包含区间[i,i+1]的线段。这a个线段的交集的期望即每个区间的贡献总和。
  • a个线段，有b个线段覆盖区间[j,j+1]，则区间[j,j+1]的。这个循环统计完时，我们尚未减去考虑所有线段都不选的情况，即上面👆贡献中的的“-1”；最后，将除，得到答案期望。

    AC代码

    #include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=4e6+10,mod=998244353,inf=1e9+1,ny=499122177;//2的逆元 
long long a[M],b[M],p[N],ans;
int l[N],r[N],L[N],R[N];
bool cmp1(int x,int y)
{
  return l[x]<l[y];
}
bool cmp2(int x,int y)
{
  return r[x]<r[y];
}
void build(int x,int l,int r)
{
  a[x]=p[r+1]-p[l],b[x]=1;
  if(l==r) return;
  int m=(l+r)>>1;
  build(x*2,l,m);
  build(x*2+1,m+1,r);
}
void find(int x,int l,int r,long long y,int L,int R)//将区间[l,r]的权值都乘y 
{
  if(l<=L && r>=R)
  {
      (a[x]*=y)%=mod,(b[x]*=y)%=mod;
      return;
  }
  int m=(L+R)>>1;
  if(l<=m) find(x*2,l,r,y,L,m);
  if(r>m) find(x*2+1,l,r,y,m+1,R);
  a[x]=(a[x*2]+a[x*2+1])*b[x]%mod;
}
int main()
{
  int n,m=2,x=1,y=1,i;
  p[1]=0,p[2]=inf;
  scanf("%d",&n);
  for(i=1;i<=n;i++)
  {
      scanf("%d%d",&l[i],&r[i]);
      p[++m]=l[i],p[++m]=++r[i],L[i]=i,R[i]=i;
  }
  sort(p+1,p+m+1);
  m=unique(p+1,p+m+1)-p-1;
  build(1,1,m-1);
  for(i=1;i<=n;i++)
  {
      l[i]=lower_bound(p+1,p+m+1,l[i])-p;
      r[i]=lower_bound(p+1,p+m+1,r[i])-p;
  }
  sort(L+1,L+n+1,cmp1);
  sort(R+1,R+n+1,cmp2);
  for(i=1;i<=m-1;i++)
  {
      while(x<=n && l[L[x]]<=i)//添加左端点小于等于i的线段的贡献，等于该区间的权值*2
          find(1,l[L[x]],r[L[x]]-1,2,1,m-1),x++;
      while(y<=n && r[R[y]]<=i)//删除右端点小于等于i的线段的贡献，等于该区间的权值-2
          find(1,l[R[y]],r[R[y]]-1,ny,1,m-1),y++;
      (ans+=a[1]*(p[i+1]-p[i]))%=mod;
  }
  (ans+=mod-1ll*inf*inf%mod)%=mod;
  for(i=1;i<=n;i++) (ans*=ny)%=mod;
  printf("%lld\n",ans);
  return 0;
}