看起来$O(nlogn)$可过其实由于巨大常数是无法通过的
$O(nlogn)$：70pts
我们手玩样例发现
线段树上某个节点的期望值$f[o]=(f[lc]+f[rc])/2+sum[o]$
$s[o]$表示该节点代表的区间和。
每次$Add(l,r,x)$时，每个x对于$f[o]$的贡献是固定的，即$f[o]+=x*k[o]$
这个$k[o]$可以在建树时预处理。
然鹅卡不过TAT
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef double db;
typedef long long ll;
template <typename T> void read(T &x){
static char c=getchar();x=; bool f=;
while(c<''||c>'') f=f&&(c!='-'),c=getchar();
while(''<=c&&c<='') x=x*+(c^),c=getchar();
x=f?x:-x;
}
#define N 4000005
int n,m,qwq; db f[N],k[N]; ll s[N],add[N];
#define lc o<<1
#define rc o<<1|1
#define mid (l+r)/2
inline void up(int o){s[o]=s[lc]+s[rc],f[o]=(f[lc]+f[rc])/2.0+s[o];}
void down(int o,int l,int r){
if(add[o]==) return ;
s[lc]+=1ll*(mid-l+)*add[o]; s[rc]+=1ll*(r-mid)*add[o];
f[lc]+=k[lc]*add[o]; f[rc]+=k[rc]*add[o];
add[lc]+=add[o]; add[rc]+=add[o]; add[o]=;
}
void build(int o,int l,int r){
if(l==r){read(s[o]); f[o]=s[o]; k[o]=1.0; return ;}
build(lc,l,mid); build(rc,mid+,r);
k[o]=+(k[lc]+k[rc])/2.0+(db)(r-l+); up(o);
}
void Add(int o,int l,int r,int x1,int x2,int v){
if(x1<=l&&r<=x2){
s[o]+=1ll*(r-l+)*v; f[o]+=k[o]*(db)v; add[o]+=v;
return ;
}down(o,l,r);
if(x1<=mid) Add(lc,l,mid,x1,x2,v);
if(x2>mid) Add(rc,mid+,r,x1,x2,v);
up(o);
}
int main(){
read(n);read(m);read(qwq); int q1,q2,q3;
build(,,n);
while(m--){
read(q1);read(q2);read(q3);
Add(,,n,q1,q2,q3);
printf("%.0lf\n",f[]*(db)qwq);
}return ;
}
$O(n)$：100pts
我们直接看每个叶节点对答案的贡献
贡献$=$概率$*$从根节点到该叶节点上的各点权值和
概率在建树时即可预处理，而权值和在询问时可以顺便处理掉
每次$Add(l,r,x)$时，考虑每个$x$对答案的贡献
$x \times \sum_{i=1}^{dep}{\frac{1}{2^{i-1}}}$
后面的东西是等比数列，可以化成$\frac{2^{dep}-1}{2^{dep-1}}$
区间修改的话就维护这个东西的前缀和
于是我们算出所有期望和再直接除以$2^{maxd}$就好辣
注意$2^{maxd}$与$qwq$需要约分，防爆精度
#include<iostream>
#include<cstdio>
#include<cstring>
typedef double db;
typedef long long ll;
inline int Max(int a,int b){return a>b?a:b;}
template <typename T> void read(T &x){
static char c=getchar();x=; bool f=;
while(c<''||c>'') f=f&&(c!='-'),c=getchar();
while(''<=c&&c<='') x=x*+(c^),c=getchar();
x=f?x:-x;
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
#define N 1000005
int n,m,Md; ll sum[N<<],s[N],ans,y,qwq,d[N];
#define lc o<<1
#define rc o<<1|1
#define mid (l+r)/2
void build(int o,int l,int r,int D){
if(l==r){
read(sum[o]); d[l]=D; Md=Max(Md,D);
return ;
}build(lc,l,mid,D+); build(rc,mid+,r,D+);
sum[o]=sum[lc]+sum[rc];
}
ll Ask(int o,int l,int r,int t,ll tt){
if(l==r) return 1ll*(1ll<<t)*(tt+sum[o]);
return Ask(lc,l,mid,t-,tt+sum[o])+
Ask(rc,mid+,r,t-,tt+sum[o]);
}
int main(){
read(n);read(m);read(qwq); int q1,q2,q3;
build(,,n,);
ans=Ask(,,n,Md-,); y=1ll<<(Md-);
ll g=gcd(qwq,y); qwq/=g; y/=g;
for(int i=;i<=n;++i)
s[i]=s[i-]+1ll*((1ll<<d[i])-)*(1ll<<(Md-d[i]));
while(m--){
read(q1);read(q2);read(q3);
ans+=1ll*(s[q2]-s[q1-])*q3;
printf("%lld\n",ans/y*qwq);
}return ;
}