Category:LOJ概率期望数据结构线段树
Article From:https://www.cnblogs.com/luyouqi233/p/9121517.html

https://loj.ac/problem/2537

Refer to the few questions that can be found on the Internet.

And my eyes do not see the need to disperse, and do not see longlong ancestors.

————————————————————————————

It is easy to see that our operation is equivalent to merging two sets of data and renewing the expectation of each number.

The weight line tree can help us achieve this function (of course, we need to dynamically open point).

Then we think about the merging of the line tree.orzBut I won’t

Let’s expect the left son’s number u to be his father’s weight, and the probability that his father chooses the maximum is k, and u is set to w in the right son number set than the smaller number.

The probability is pu* ((1-W) * (1-k) +w*k) =pu* (1-w-k+2*w*k).

Of course, the right son is the same.

Of course, statistical w can obviously not be violent. Our weight line tree maintains the expected sum of all the numbers selected in the current interval, and all possible maximum intervals from left to right. This interval satisfies the number set of a son that does not contain any number in this interval.

The expectation of this interval can be reduced to the “expectation of a number”, and the W is easily calculated at this time, which is equivalent to the expectation of all the numbers before the interval, and then O (1) can be obtained after each interval is added, then it is converted to the interval modification problem.

```#include<cmath>
#include<queue>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=3e5+5;
const int p=998244353;
int X=0,w=0;char ch=0;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
return w?-X:X;
}
int qpow(int k,int n){
int res=1;
while(n){
if(n&1)res=(ll)res*k%p;
k=(ll)k*k%p;n>>=1;
}
return res;
}
struct tree{
int l,r;
ll p,lazy;
}tr[N*20];
int fa[N],son[N],ch[N][2],rt[N],pool,n,m,b[N],q[N];
inline void LSH(){
sort(b+1,b+m+1);
m=unique(b+1,b+m+1)-b-1;
for(int i=1;i<=n;i++)
if(!son[i])
q[i]=lower_bound(b+1,b+m+1,q[i])-b;
}
void insert(int &x,int l,int r,int k){
tr[x=++pool].p=1;tr[x].lazy=1;
if(l==r)return;
int mid=(l+r)>>1;
if(k<=mid)insert(tr[x].l,l,mid,k);
else insert(tr[x].r,mid+1,r,k);
}
inline void push(int x){
if(tr[x].lazy<=1)return;
(tr[tr[x].l].lazy*=tr[x].lazy)%=p;
(tr[tr[x].r].lazy*=tr[x].lazy)%=p;
(tr[tr[x].l].p*=tr[x].lazy)%=p;
(tr[tr[x].r].p*=tr[x].lazy)%=p;
tr[x].lazy=1;
}
int maxl,maxr;
int merge(int nl,int nr,int l,int r,int k){
if(!nl&&!nr)return 0;
if(!nl){
(maxr+=tr[nr].p)%=p;
(tr[nr].p*=((ll)2*maxl%p*k%p-k-maxl+1)%p+p)%=p;
(tr[nr].lazy*=((ll)2*maxl%p*k%p-k-maxl+1)%p+p)%=p;
return nr;
}
if(!nr){
(maxl+=tr[nl].p)%=p;
(tr[nl].p*=((ll)2*maxr%p*k%p-k-maxr+1)%p+p)%=p;
(tr[nl].lazy*=((ll)2*maxr%p*k%p-k-maxr+1)%p+p)%=p;
return nl;
}
push(nl);push(nr);
int mid=(l+r)>>1;
tr[nl].l=merge(tr[nl].l,tr[nr].l,l,mid,k);
tr[nl].r=merge(tr[nl].r,tr[nr].r,mid+1,r,k);
tr[nl].p=(tr[tr[nl].l].p+tr[tr[nl].r].p)%p;
return nl;
}
void dfs(int u){
if(!son[u]){
insert(rt[u],1,m,q[u]);return;
}
if(son[u]==1){
dfs(ch[u][0]);
rt[u]=rt[ch[u][0]];
}else{
dfs(ch[u][0]);dfs(ch[u][1]);
maxl=maxr=0;
rt[u]=merge(rt[ch[u][0]],rt[ch[u][1]],1,m,q[u]);
}
}
int cnt;
int query(int x,int l,int r){
if(!tr[x].p)return 0;
if(l==r){
cnt++;
return (ll)cnt*b[l]%p*tr[x].p%p*tr[x].p%p;
}
push(x);
int mid=(l+r)>>1;
return (query(tr[x].l,l,mid)+query(tr[x].r,mid+1,r))%p;
}
int main(){
for(int i=1;i<=n;i++){
ch[fa[i]][son[fa[i]]++]=i;
}
int inv=qpow(10000,p-2);
for(int i=1;i<=n;i++){
if(son[i])q[i]=(ll)q[i]*inv%p;
else b[++m]=q[i];
}
LSH();
dfs(1);
printf("%d\n",query(rt[1],1,m));
return 0;
}```

+++++++++++++++++++++++++++++++++++++++++++