【CERC2017】Cumulative Code

Description:


设深度为 k的满二叉树的\(\mathrm{Pr\ddot{u}fer}\)编码序列为\(P=\{p_i\}\)

\(m\)次询问,对于每次询问给出 a d m,求\(\sum\limits_{i=0}^{m-1}p_{a+i\times d}\)

\(2\leq k \leq 30 , 1 \leq q \leq 300\)

Examples:


input1output1
3 5
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1
2
2
1
3
3
input2output2
4 4
2 1 5
4 4 3
4 8 1
10 3 2
18
15
5
13
input3output3
7 1
1 1 125
4031

Solution:


太神了!

考虑暴力搜索,搜索状态为 search(x, k),表示以\(x\)为根深度为\(k\)的子树的\(\mathrm{Pr\ddot{u}fer}\)编码中对答案的贡献。为了方便顺便维护两个值 i m分别表示在删除这个子树之前已经删了多少个点,在这棵子树的\(\mathrm{Pr\ddot{u}fer}\)编码中有多少点属于等差数列。

这样 search(x, k)可以递归到 search(2 * x, k - 1), search(2 * x + 1, k - 1),还要考虑下根节点是否属于等差数列,并且根节点,左子树,右子树的删除顺序和根节点是否有父边也有关系,需要处理一下。

但是这样复杂度会是\(\mathcal{O}(2^k)\),需要优化。

然后很神的就是将搜索状态设为 solve(k, i, m, hasfa)hasfa表示根节点是否有父边, ret表示根节点为\(x\),深度为\(k\)的满二叉树,之前已有\(i\)位\(\mathrm{Pr\ddot{u}fer}\)编码,子树的编码中接下来还有\(m\)个所需的位的答案为\(ret.a\times x+ret.b+c\times \left \lfloor \frac{x}{2} \right \rfloor \),这样统计答案的好处在于答案的值是关于根节点的函数,答案的值只与所需点的相对位置有关,而与根节点无关。在不影响左右子树答案的合并的前提下,有利于之后的记忆化搜索。

设当前节点(根节点为x)目前答案为\(ret.a, ret.b, ret.c\)左子树(根节点为2x+1)答案为\(son.a, son.b, son.c\),根据定义合并后\(\begin{split}ans&=ret.a\times x+ret.b+ret.c\times \left \lfloor \frac{x}{2} \right \rfloor + son.a\times (2x)+son.b+son.c\times \left \lfloor \frac{2x}{2} \right \rfloor \\&=(ret.a+2\times son.a+son.c)\times x+(ret.b+son.b)+ret.c\times \left \lfloor \frac{x}{2} \right \rfloor\end{split}\)

右子树同理。

接下来则是记忆化需要记录的状态,首先,只有当该子树对应的编码区间属于\([a,a+(m-1)\times d]\),且该子树有父边才进行记忆化。于是,记录的状态为 g[k][i], 表示根节点有父边,根节点为\(x\),深度为\(k\)的满二叉树,且任意\(p’_{i+j*d}\)均为所需点的答案为\(g[k][i].a\times x+g[k][i].b+g[k][i].c \times \left \lfloor \frac{x}{2} \right \rfloor (P’=\{p’_i\}为该子树的编码序列)\),因为所有有父边深度为\(k\)的满二叉树删除顺序是一定的,每次询问\(d\)又是固定的,所以选取的相对位置的集合(即答案)只与该子树编码中第一个被选取的点的 offset有关。

为了保证复杂度,只记录\(k\leq 15\)的状态。状态总数最多为\(15 \times (2^{15}-1)\)

然后考虑每次搜索时间复杂度,

  1. 当\(15<k\leq 30\), 最多只会搜索\(2^{15}\)次
  2. 当\(1\leq k \leq 15\),不能记忆化的区间只有\(\mathcal{O}(k)\)个,没有父边的区间最多也只有\(\mathcal{O}(k)\)个

所以单次询问复杂度为\(\mathcal{O}(2^{\frac{k}{2}})\)

Code:


 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注