挺妙的一道期望題

首先經過一番簡單的思考就會發現對于線段樹上的一個葉子節點\(x\)，深度為\(deep[x]\)，那么走到這個節點的概率就是\(2^{deep[x]}\)

我們設\(val[x]\)表示葉節點\(x\)到根經過的所有節點的權值和為\(val[x]\)

于是最后的答案就是

\[qwq*\sum_{i=1}^{n}\frac{val[i]}{2^{deep[i]}}\]

連分母都不一樣，于是先通分一下吧

\[qwq*\sum_{i=1}^n\frac{val[i]*2^{maxdep-deep[i]}}{2^{maxdep}}\]

但是要是遇上了區間修改呢，我們完全沒有辦法維護\(val[i]\)

好像遇上了瓶頸

于是我們換一個思路，對整棵線段樹來考慮，在算概率的時候，顯然樹上有很多節點是被多次計入答案的

比如對于線段樹上的節點\([1,n]\)每一個點的\(val\)都算入了這個點

這具有非常妙的性質

我們暫且將分子上的\(2^{maxdep-deep[i]}\)稱為葉節點的權，那么一個線段樹上的非葉節點的總權值就是其內部所有葉子節點的權的和，就是子樹和

那么這個子樹和顯然就表示在最終計入答案的時候，這個線段樹上的節點管轄的區間和應該乘上多少次

那么我們現在的答案就可以寫成

\[qwq*\sum_{i=1}^M\frac{sum[i]*d[i]}{2^{maxdep}}\]

\(sum[i]\)表示子樹和，\(d[i]\)表示線段樹上的節點\(i\)所管轄的區間和，\(M\)為線段樹的節點個數

現在再來考慮一下修改一個節點會對整個線段樹產生什么樣的影響

顯然就是從這個節點一直往上直到根所有節點的管轄的區間和都會相應的增加

我們設\(pre[i]\)(可以理解為根路徑前綴和)表示\(i\)這個節點到根節點經過的所有節點的\(sum\)的和為多少，如果這次修改的增量為\(k\)，那么對于整個線段樹的答案的貢獻就是\(pre[i]*k\)

之后就會發現好像每一個單點之間的修改互不影響，于是如果對一個區間\([x,y]\)進行修改的話對答案的貢獻就是\(k*\sum_{i=x}^ypre[i]\)

于是我們直接對\(pre\)數組做出一個前綴和就可以快速回答了

代碼

#include<iostream> #include<cstdio> #include<cstring> #define re register #define LL long long #define max(a,b) ((a)>(b)?(a):(b)) #define maxn 1000005 inline int read() {re char c=getchar();re int x=0,r=1;while(c<'0'||c>'9') {if(c=='-') r=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48,c=getchar();return x*r; } inline void write(LL x) {if(x>9) write(x/10);putchar(x%10+48); } int a[maxn]; int deep[maxn]; int p[maxn],val[maxn]; LL sum[maxn<<2],pre[maxn]; int n,Q,qwq,maxdep; LL ans,FM; void build(int x,int y,int dep,LL Sum)//求出所有葉節點的深度，和val {if(x==y){deep[x]=dep;val[x]=Sum;maxdep=max(maxdep,dep);return;}int mid=x+y>>1;build(x,mid,dep+1,Sum+p[mid]-p[x-1]),build(mid+1,y,dep+1,Sum+p[y]-p[mid]); } LL dfs(int x,int y,int i)//求出線段樹上所有點的子樹和 {if(x==y) return sum[i]=1ll<<(maxdep-deep[x]);int mid=x+y>>1;return sum[i]=dfs(x,mid,i<<1)+dfs(mid+1,y,i<<1|1); } void Pre_Dfs(int x,int y,int i,LL Sum)//求出每一個節點的pre值 {if(x==y){pre[x]=Sum;return;}int mid=x+y>>1;Pre_Dfs(x,mid,i<<1,Sum+sum[i<<1]),Pre_Dfs(mid+1,y,i<<1|1,Sum+sum[i<<1|1]); } inline LL gcd(LL a,LL b) {if(!b) return a;return gcd(b,a%b); } int main() {n=read(),Q=read(),qwq=read();for(re int i=1;i<=n;i++) a[i]=read(),p[i]=p[i-1]+a[i];build(1,n,0,p[n]);dfs(1,n,1);Pre_Dfs(1,n,1,sum[1]);for(re int i=1;i<=n;i++) pre[i]=pre[i-1]+pre[i];for(re int i=1;i<=n;i++) ans+=val[i]*(1ll<<(maxdep-deep[i]));//先求出最開始的答案int x,y,z;FM=1ll<<maxdep;LL r=gcd(qwq,FM);qwq/=r,FM/=r;//約分，防止爆long longwhile(Q--){x=read(),y=read(),z=read();ans+=(pre[y]-pre[x-1])*z;if(ans>0) write(qwq*ans/FM);else putchar('-'),write(-qwq*ans/FM);putchar(10);}return 0; }

轉載于:https://www.cnblogs.com/asuldb/p/10206191.html

總結

以上是生活随笔為你收集整理的【康娜的线段树】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。