题解 P3924 【康娜的线段树】

## 上面两位dalao谈笑风生就讲完了这道题，但身为蒟蒻的我一窍不通，好不容易想通了写个题解纪念一下。 2018 09 14 upd:感谢[@cqxxx](https://www.luogu.org/space/show?uid=80885)大佬指正了题解里的错误。致敬！ 2018 09 15 upd:再次感谢[@cqxxx](https://www.luogu.org/space/show?uid=80885)大佬与我的交流，终于全面地解决了这道题。再次致敬！ --- 这道题要维护一个线段树里面的期望。期望是这么计算的： > 如果每次在线段树区间加操作做完后，从根节点开始等概率的选择一个子节点进入，直到进入叶子结点为止，将一路经过的节点权值累加，最后能得到的期望值是多少？ ## 最朴素计算期望的思路 根结点权值乘以1 + 所有第二层结点权值和乘以二分之一 + 所有第三层结点权值和乘以四分之一 直到到达叶子结点为止，把这些东西都加起来就是答案。 ## 一个优化的思路 因为从根节点开始进入，每一个唯一的路径会走向唯一的叶子结点，所以我们可以直接维护每个叶子结点的期望。 每个叶子结点对答案的贡献值其实就是**从根结点到达这个叶子结点路径经过的所有点权值和除以$2^{dep - 1}$**。可以证明答案是不会变的，因为每个结点因为深度关系一定会被走固定多次。 这里用到一个简便运算的细节：对于每个结点的贡献都要除以$2^{dep-1}$，我们可以在建树的时候预处理出叶子结点最大深度$maxd$。 然后我们算出各节点权值和乘以$2^{maxd - dep}$，再共同除以$2^{maxd-1}$就是答案了。 ## 前缀和维护 经过上面的分析我们发现这个答案就只跟叶子结点的深度有关了。（无法理解的看上面黑体字，然后画个线段树模拟一下） 所以我们可以直接通过维护单个叶子结点对答案的贡献来维护答案的增加。 我们跳回原来的思路。先考虑单节点的加。 是不是从根结点到这个叶子结点的相应值都会增加$x$这么多？ 所以单节点值增加$x$，答案就会增加 $$x \times \sum_{i=1}^{dep}{\frac{1}{2^{i-1}}}$$ 发现这个东西就是个等比数列，很容易地化简为$1 + 1 - \frac{1}{2^{dep-1}} = 2 - \frac{1}{2^{dep-1}} = \frac{2^{dep}-1}{2^{dep-1}}$。 区间加也好维护，直接弄个前缀和就是了。可以直接乘上去。 ## 代码 代码是参考标算的，反手%一波zcy大佬。 ```cpp #include<cstdio> #include<algorithm> #define ll long long #define lson (root << 1) #define rson (root << 1 | 1) const int maxn = 1000005; ll sum[maxn << 2], lazy[maxn << 2]; ll a[maxn], dep[maxn]; ll s[maxn]; ll n, m, qwq; ll maxd; ll read() { ll ans = 0, s = 1; char ch = getchar(); while(ch > '9' || ch < '0'){ if(ch == '-') s = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); return s * ans; } void build(ll root, ll l, ll r, ll d)//相比一般的线段树多统计了深度，并维护最大深度 { if(l == r) { sum[root] = a[l]; dep[l] = d; maxd = std::max(maxd, d); return; } ll mid = (l + r) >> 1; build(lson, l, mid, d + 1); build(rson, mid + 1, r, d + 1); sum[root] = sum[lson] + sum[rson]; } ll query(ll root, ll l, ll r, ll t, ll tt)//tt表示当前结点以上的那些结点权值和，t的意义看下面 { if(l == r) return (1 << t) * (tt + sum[root]);//返回的值是所有的叶子节点，返回值是路径权值和 乘以 2^(maxd - dep[i]) ll mid = (l + r) >> 1; return query(lson, l, mid, t - 1, tt + sum[root]) + query(rson, mid + 1, r, t - 1, tt + sum[root]); } ll gcd(ll x, ll y) { if(y == 0) return x; return gcd(y, x % y); } int main() { n = read(), m = read(), qwq = read(); for(int i = 1; i <= n; i++) a[i] = read(); build(1, 1, n, 1); ll ans = query(1, 1, n, maxd - 1, 0), y = 1 << (maxd - 1); ll yue = gcd(y, qwq);//约分，别中途超出范围了 y /= yue; qwq /= yue; for(ll i = 1; i <= n; i++) s[i] = s[i - 1] + (((1 << dep[i]) - 1) << (maxd - dep[i])); //后面加的式子其实是(2^(dep[i]) - 1) * 2^(maxd - dep[i]) while(m--) { ll l = read(), r = read(), w = read(); ans += (s[r] - s[l - 1]) * w; printf("%lld\n", ans / y * qwq);// ans / y是真正的期望，y取2^(maxd - 1) } return 0; } ```