Codeforces 68D - Half-decay Tree

题意

有一颗高度为 \(h\) 的完全二叉树（即点数为 \(2^{h+1}-1\) ），有两种操作：

• add x y 给 \(x\) 点的权值加 \(y\)
• decay 一次衰变定义为选择一个叶子节点，断掉它到根的所有边，这样整个树会变成很多个连通块，一个连通块的权值是其中所有点的权值和；这个衰变的权值为这些连通块的权值中的最大值。这个操作要求输出随机选一个叶子进行衰变的期望权值。（衰变之间互不影响）

\(h\le 30,q\le 10^5\) 。

分析

一般这种完全二叉树都要利用其深度很小的性质。

可以发现，衰变的时候，最终得到的连通块都是由一个点和其一个子树构成的。对衰变求期望其实是求所有节点的衰变权值和。

对于一个点 \(x\) ，设其左儿子的子树权值和为 \(s_l\) ，右儿子的子树权值和为 \(s_r\) ，那么显然，若 \(s_l\ge s_r\) ，那么右子树中的所有点在衰变的时候，所取到的最大连通块都不可能使右子树中的。所以我们用当前的 \(\max\) 和左子树加当前点即可直接计算右子树的答案，接着递归进入左子树即可。

我们要维护的东西就是子树的权值和。

因此单次操作是 \(O(h\log n)\) 的（用 map ）。

代码

#include<bits/stdc++.h>

#include<ext/pb_ds/assoc_container.hpp>

#include<ext/pb_ds/hash_policy.hpp>

using namespace std;

typedef __gnu_pbds::cc_hash_table<int,int> Map;

typedef long long giant;

inline char nchar() {

	static const int bufl=1<<20;

	static char buf[bufl],*a=NULL,*b=NULL;

	return a==b && (b=(a=buf)+fread(buf,1,bufl,stdin),a==b)?EOF:*a++;

}

template<class T> inline T read() {

	T x=0,f=1;

	char c=nchar();

	for (;!isdigit(c);c=nchar()) if (c=='-') f=-1;

	for (;isdigit(c);c=nchar()) x=x*10+c-'0';

	return x*f;

}

template<> char read<char>() {

	char c=nchar();

	for (;!isalpha(c);c=nchar());

	for (char f=nchar();isalpha(f);f=nchar());

	return c;

}

int h,q,last;

namespace tree {

	Map sum;

	void add(int x,int d) {

		for (;x;x>>=1) sum[x]+=d;

	}

	inline int size(int x) {

		return 1<<(h-(31-__builtin_clz(x)));

	}

	giant calc(int x,int mx) {

		if (x>=last) return max(mx,sum[x]);

		int lc=x<<1,rc=lc+1,sl=sum[lc],sr=sum[rc],sx=sum[x];

		giant ret=0;

		if (sl>sr) swap(lc,rc),swap(sl,sr);

		ret=(giant)size(lc)*max(sx-sl,mx);

		ret+=calc(rc,max(mx,sx-sr));

		return ret;

	}

	long double ans() {

		long double ret=calc(1,0);

		ret/=last;

		return ret;

	}

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("test.in","r",stdin);

#endif

	h=read<int>(),q=read<int>(),last=1<<h;

	while (q--) {

		char o=read<char>();

		if (o=='a') {

			int x=read<int>(),y=read<int>();

			tree::add(x,y);

		} else printf("%.12lf\n",(double)tree::ans());

	}

	return 0;

}