思路

这道题很好，很有趣。

如果您是神仙的话呢，可以考虑直接线段是卡掉本题（有人试过了），但是我这个菜鸡不行，所以写了题解的\(O(1)\)询问解法。

首先，树形 DP 的方程为：

\[ dp[u] = \frac{1}{2} * (dp[lson]+dp[rson]) \]

我们观察叶子节点对答案的贡献，发现为该条链上的权值和除掉\(2^{dep-1}\)，也就是与深度有关。那么，为了简化答案，我们可以把这个写作：

\[ \frac{1}{2^{dep-1}} = 2^{1-dep} = \frac { 2^{maxDep – dep} }{ 2^{maxDep-1} } \]

就变成了乘法形式。我们在讨论询问的问题。在区间\([l,r]\)之间加上\(x\)，链对答案的贡献是：

\[ x · \sum_{i = 1}^{dep} \frac{1}{2^{i-1}} \]

所以，维护一个前缀和，往答案上面加上前缀和段和这个贡献的积即可获得答案。（记得用 gcd 约分）

代码

// P3924.cpp
#include <bits/stdc++.h>
#define ll long long
#define mid ((l + r) >> 1)
#define lson (p << 1)
#define rson ((p << 1) | 1)
using namespace std;
const int MAX_N = 1e6 + 2000;
ll n, m, qwq, sum[MAX_N << 2], depth[MAX_N << 2], arr[MAX_N], s[MAX_N], max_dep;
inline ll read()
{
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}
void build(ll l, ll r, ll dp, ll p)
{
    if (l == r)
    {
        sum[p] = arr[l], depth[l] = dp, max_dep = max(max_dep, dp);
        return;
    }
    build(l, mid, dp + 1, lson), build(mid + 1, r, dp + 1, rson);
    sum[p] = sum[lson] + sum[rson];
}
ll query(ll l, ll r, ll p, ll dep, ll prefix)
{
    if (l == r)
        return (1 << dep) * (prefix + sum[p]);
    return query(l, mid, lson, dep - 1, prefix + sum[p]) + query(mid + 1, r, rson, dep - 1, prefix + sum[p]);
}
ll gcd(ll a, ll b) { return (b == 0) ? a : gcd(b, a % b); }
int main()
{
    n = read(), m = read(), qwq = read();
    for (int i = 1; i <= n; i++)
        arr[i] = read();
    build(1, n, 1, 1);
    ll ans = query(1, n, 1, max_dep - 1, 0), dominator = 1 << (max_dep - 1);
    ll fact = gcd(dominator, qwq);
    dominator /= fact, qwq /= fact;
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + (((1 << depth[i]) - 1) << (max_dep - depth[i]));
    while (m--)
    {
        ll l = read(), r = read(), w = read();
        ans += (s[r] - s[l - 1]) * w;
        printf("%lld\n", ans / dominator * qwq);
    }
    return 0;
}