2020牛客暑期多校训练营（第九场）C-Groundhog and Gaming Time

题目大意

给定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;
  }