P3924 康娜的线段树

题目描述

小林是个程序媛，不可避免地康娜对这种人类的“魔法”产生了浓厚的兴趣，于是小林开始教她OI。

P3924 康娜的线段树-LMLPHP

今天康娜学习了一种叫做线段树的神奇魔法，这种魔法可以维护一段区间的信息，是非常厉害的东西。康娜试着写了一棵维护区间和的线段树。由于她不会打标记，因此所有的区间加操作她都是暴力修改的。具体的代码如下：(略)

显然，这棵线段树每个节点有一个值，为该节点管辖区间的区间和。

康娜是个爱思考的孩子，于是她突然想到了一个问题：

如果每次在线段树区间加操作做完后，从根节点开始等概率的选择一个子节点进入，直到进入叶子结点为止，将一路经过的节点权值累加，最后能得到的期望值是多少？

康娜每次会给你一个值 qwq ，保证你求出的概率乘上 qwq 是一个整数。

这个问题太简单了，以至于聪明的康娜一下子就秒了。

现在她想问问你，您会不会做这个题呢？

$n, m <= 10^{6}$

Solution

单点将叶子结点$k$ 加上 $x$ ，由于线段树的结构，设此节点处于线段树第 $dep[k]$ 层，有答案加上：

\[x * \sum_{i = 0}^{dep[k] - 1}{\frac{1}{2^{i}}}$$$$=x * \frac{2^{n} - 1}{2^{n - 1}}(n = dep[k])
\]

然后区间修改可以视为多次单点修改，互相不构成影响，令 $a[i] = \frac{2^{n} - 1}{2^{n - 1}}$ ，固有 $l, r$ 的修改总答案加上：

\[x * \sum_{i = l}^{r}{a[i]}
\]

可以以前缀和维护 $a[i]$ ，故式子变为：

\[(sum[r] - sum[l - 1]) * x
\]

可以在 $O(1)$ 的时间内完成一次询问

现在只需要求解每个叶子节点的深度即可

处理数据的时候有可能在前缀和部分无法很好的解决精度问题，为了简便运算，令所有的 $a[i] *= 2^{maxdep}$ ，这样每个 $a[i]$ 就变成了

\[(2^{n} - 1) * (2^{maxdep - n + 1})
\]

在输出的时候统一再除以 $frac = 2^{maxdep}$ 即可

输出为：$$(sum[r] - sum[l - 1]) * x / frac * qwq$$

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#include<climits>

#define LL long long

#define REP(i, x, y) for(LL i = (x);i <= (y);i++)

using namespace std;

LL RD(){

    LL out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const LL maxn = 2000019;

LL num, na, qwq;

LL v[maxn], dep[maxn], maxdep;

LL ans;

#define lid (id << 1)

#define rid (id << 1) | 1

struct seg_tree{

	LL l, r;

	LL sum;

	}tree[maxn << 2];

void build(LL id, LL l, LL r, LL d){

	tree[id].l = l, tree[id].r = r;

	if(l == r){

		tree[id].sum = v[l];

		dep[l] = d;

		maxdep = max(maxdep, d);

		return ;

		}

	LL mid = (l + r) >> 1;

	build(lid, l, mid, d + 1), build(rid, mid + 1, r, d + 1);

	tree[id].sum = tree[lid].sum + tree[rid].sum;

	}

void dfs(LL id, LL d){

	ans += tree[id].sum * (1 << (maxdep - d + 1));

	if(tree[id].l == tree[id].r)return ;

	dfs(lid, d + 1), dfs(rid, d + 1);

	}

LL gcd(LL a, LL b){return !b ? a : gcd(b, a % b);}

LL a[maxn], sum[maxn];

int main(){

	num = RD(), na = RD(), qwq = RD();

	REP(i, 1, num)v[i] = RD();

	build(1, 1, num, 1), dfs(1, 1);

	LL frac = 1 << maxdep;

	LL d = gcd(frac, qwq);

	frac /= d, qwq /= d;

	REP(i, 1, num){

		a[i] = ((1 << dep[i]) - 1) * (1 << (maxdep - dep[i] + 1));

		sum[i] = sum[i - 1] + a[i];

		}

	while(na--){

		LL l = RD(), r = RD(), x = RD();

		ans += (sum[r] - sum[l - 1]) * x;

		printf("%lld\n", ans / frac * qwq);

		}

	return 0;

	}