我们可以画图找规律

这里没图,要看图可以去看M_sea dalao的题解(逃

可以发现单个节点\(i\)对答案的贡献为该节点的点权\(*\frac{1}{2^{dep_i}}\)(\(dep_i\)为从上往下\(i\)节点所在的层数-1,也就是深度,令根节点的\(dep=0\))

我们可以发现,所有叶子节点的深度都是最大深度(记为\(ma\))或者最大深度-1,所以除开最下面一层,从上往下第\(i\)层的贡献都是序列中所有数之和\(*\frac{1}{2^{i-1}}\),最下面一层的每个叶子节点的贡献就是点权\(*\frac{1}{2^{ma}}\).为了方便,下面算答案时把所有数\(*2^{ma}\),输出的时候再除掉

我们先预处理最初的答案,记\(b=\sum_{j=1}^{ma}2^j\),序列中第\(i\)个数的贡献为\(a_i*(b+[dep_{i\text{在线段树中对应的叶子节点}}=ma])\)(如果是最后一层就多加上\(a_i\)是吧) 这里字不太好看先憋着

每次的区间加法,记\(c=\)区间内深度为\(ma\)的叶子节点个数,可以发现答案加上了\(x*(r-l+1)*b+x*c\)

最后答案要\(/2^{ma}*qwq\),并且注意将\(2^{ma}\)和\(qwq\)约分,不然会爆\(long\ long\)

我做题时居然那啥到强行用树状数组求前缀和qwq

// luogu-judger-enable-o2#include
    
     #define LL long long#define il inline#define re register#define db double#define max(a,b) ((a)>(b)?(a):(b))using namespace std;const int N=1000000+10;il LL rd(){    re LL x=0,w=1;re char ch=0;    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}    return x*w;}#define lc (o<<1)#define rc ((o<<1)|1)#define mid ((l+r)>>1)int n,m,a[N],mm;LL qwq,b=1,ans,c[N];void init(int k,int l,int r){  if(l==r){mm=max(mm,a[l]=k);return;}  init(k+1,l,mid),init(k+1,mid+1,r);}il LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}int main(){  n=rd(),m=rd(),qwq=rd();  init(0,1,n);  b=(1ll<<(mm+1))-2;    //这就是题解中的b  for(re int i=1;i<=n;i++)    {      LL x=rd();      ans+=x*b;      c[i]+=c[i-1];      if(a[i]==mm) ++c[i],ans+=x;    }  mm=1ll<