要是一眼看出来就不用写博客了

感觉可以用简单的容斥得到答案。即考虑每个区间对答案的贡献。这是唯一可行的路径。

但是这题难就难在不能一眼看出式子。不妨先考虑较为简单的情形，如果最终线段树上存在节点$[L,r]$，那么概率为$\frac{1}{r-L+1}$，这是非常容易看出来的。如果存在节点$[l,r]$呢？条件概率嘛，两端点应该比中间的点先被选上，概率是$\frac{2}{(r-l+2)(r-l+1)}$。

然后就容斥呗。考虑区间$[l,r]$对答案的贡献。那么$[l,r]$有贡献的条件是，$[l,r]\cap [ql,qr]\ne \varnothing$，并且其父节点$[l^{\prime },r^{\prime }]⊈[ql,qr]$，很显然这两个部分是独立的，因此第二种情况只需减去$[l^{\prime },r^{\prime }]\subseteq [ql,qr]$时子结点的数目，显然用$[l^{\prime },r^{\prime }]$出现的概率乘$2$即可完成计算。第一种情况也很好处理，简单容斥一下就完了。

加了快读都过不了，你$hdu$的题还是那么恶心。

#include<bits/stdc++.h>
#define getchar() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?EOF:*S++)
#define ll long long
#define fi first
#define se second
using namespace std;
const int mod=998244353;
const int N=1e6+5;
int n,Q,ql,qr;
ll res,f[N],sumf[N],inv[N],suminv[N];
char B[1<<15],*S=B,*T=B;
inline int read()
{char c(getchar());int x(0);while(!isdigit(c))c=getchar();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();return x;
}
void write(ll a)
{if(a>9)write(a/10);putchar(a%10+48);
}
ll getsum(int l,int r){if(l>r)return 0;return suminv[r]-suminv[l-1];
}
ll solve(int l,int r){if(l>r)return 0;int len=r-l+1;return sumf[len];
}
ll solve2(int l,int r){if(l>r)return 0;return r-l+1;
}
void add(ll &x,ll y){x=(x+y)%mod;
}
int main(){n=read(),Q=read();inv[1]=suminv[1]=1;for(int i=2;i<=n+1;i++)inv[i]=(-inv[mod%i]*(mod/i)%mod+mod)%mod,suminv[i]=(suminv[i-1]+inv[i])%mod;for(int i=1;i<=n;i++)f[i]=(f[i-1]+2*inv[i]*inv[i+1])%mod;for(int i=1;i<=n;i++)sumf[i]=(sumf[i-1]+f[i])%mod;while(Q--){ql=read(),qr=read();res=0;if(ql==1&&qr==n){printf("1\n");continue;}add(res,getsum(ql,n-1)+getsum(n-qr+1,n-1)+solve(2,n-1)-solve(2,ql-1)-solve(qr+1,n-1));if(ql==1)add(res,-getsum(2,qr)*2);if(qr==n)add(res,-getsum(2,n-ql+1)*2);add(res,solve2(max(2,ql),min(qr,n-1))*2-solve(max(2,ql),min(qr,n-1))*2+1);write((res+mod)%mod);printf("\n");}
}