要是一眼看出来就不用写博客了
感觉可以用简单的容斥得到答案。即考虑每个区间对答案的贡献。这是唯一可行的路径。
但是这题难就难在不能一眼看出式子。不妨先考虑较为简单的情形,如果最终线段树上存在节点 [ L , r ] [L,r] [L,r],那么概率为 1 r − L + 1 \frac{1}{r-L+1} r−L+11,这是非常容易看出来的。如果存在节点 [ l , r ] [l,r] [l,r]呢?条件概率嘛,两端点应该比中间的点先被选上,概率是 2 ( r − l + 2 ) ( r − l + 1 ) \frac{2}{(r-l+2)(r-l+1)} (r−l+2)(r−l+1)2。
然后就容斥呗。考虑区间 [ l , r ] [l,r] [l,r]对答案的贡献。那么 [ l , r ] [l,r] [l,r]有贡献的条件是, [ l , r ] ∩ [ q l , q r ] ≠ ∅ [l,r]\cap [ql,qr]\ne \empty [l,r]∩[ql,qr]=∅,并且其父节点 [ l ′ , r ′ ] ⊈ [ q l , q r ] [l',r']\nsubseteq [ql,qr] [l′,r′]⊈[ql,qr],很显然这两个部分是独立的,因此第二种情况只需减去 [ l ′ , r ′ ] ⊆ [ q l , q r ] [l',r']\subseteq [ql,qr] [l′,r′]⊆[ql,qr]时子结点的数目,显然用 [ l ′ , r ′ ] [l',r'] [l′,r′]出现的概率乘 2 2 2即可完成计算。第一种情况也很好处理,简单容斥一下就完了。
加了快读都过不了,你 h d u hdu 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");}
}