P3924 康娜的线段树（マジやばくね）（线段树、期望、前缀和）难度⭐⭐⭐★

P3924 康娜的线段树

我觉得挺难的，マ(ma)ジ(ji)や(ya)ば(ba)く(ku)ね(ne)（不得了了）知道康娜的应该都懂

题解 P3924 【康娜的线段树】

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>

#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)
//#define int __int128
using namespace std;
typedef long long ll;//全用ll可能会MLE或者直接WA,试着改成int看会不会A
const ll N=1000007;
const ll INF=1e9+9;
const ll mod=2147483647;
const double EPS=1e-10;//-10次方约等于趋近为0
const double Pi=3.1415926535897;

template<typename T>void read(T &x)
{
    x=0;char ch=getchar();ll f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}x*=f;
}

struct node
{
    ll sum,lz,l,r;
}tree[N<<2];
ll dep[N],a[N],s[N];
ll n,m,qwq,maxd;

void build(ll p,ll l,ll r,ll d)
{
    tree[p].l=l;tree[p].r=r;
    tree[p].sum=tree[p].lz=0;
    if(l==r)
    {
        tree[p].sum=a[r];
        dep[r]=d;
        maxd=max(maxd,d);
        return ;
    }
    build(ls,l,mid,d+1);
    build(rs,mid+1,r,d+1);
    tree[p].sum=tree[ls].sum+tree[rs].sum;
}

inline ll query(ll p,ll l,ll r,ll t,ll sumt)
{
    if(l==r)return (1<<t)*(sumt+tree[p].sum);
    //返回 2^(maxd-dep)*(题目要求的从根往下走的路径上的权值和)
    return query(ls,l,mid,t-1,sumt+tree[p].sum)+query(rs,mid+1,r,t-1,sumt+tree[p].sum);
}

inline ll gcb(ll x,ll y)
{
    if(y==0)return x;
    return gcb(y,x%y);
}

int main()
{
    scanf("%lld%lld%lld",&n,&m,&qwq);
    over(i,1,n)scanf("%lld",&a[i]);
    build(1,1,n,1);
    ll ans=query(1,1,n,maxd-1,0);//2^(dep-1)
    ll y=1<<(maxd-1);
    ll yue=gcb(y,qwq);
    y/=yue,qwq/=yue;//约分防止超出数据范围

    over(i,1,n)//处理前缀和
    s[i]=s[i-1]+(((1<<dep[i])-1)<<(maxd-dep[i]));//(2^(dep[i]) - 1) * 2^(maxd - dep[i])
    while(m--)
    {
        ll l,r,k;
        scanf("%lld%lld%lld",&l,&r,&k);
        ans+=(s[r]-s[l-1])*k;
        printf("%lld\n",ans/y*qwq);//ans / y才是期望，y取2^(maxd - 1)
    }
    return 0;
}