Drazil Likes Heap

题意翻译

### 题目描述 Drazil 非常喜欢堆这个数据结构。因此他造了一段关于堆的题目： 有一个高度为 $h$ 的大根堆存储在数组内。具体情况如下： 这个堆中有恰好 $2 ^ h - 1$ 个正整数，这些正整数两两不同。这些数存储在数组 $a$ 内下标 $1$ 到 $2 ^ h - 1$ 的位置。对于任意的 $1 \lt i \lt 2 ^ h$，都有 $a[i] \lt a\left[ \left\lfloor \frac{i}{2} \right\rfloor \right]$。 现在我们想要减小这个堆的高度到 $g$，使得堆中恰好只有 $2 ^ g - 1$ 个数。为了减小高度，我们需要进行下述操作 $2 ^ h - 2 ^ g$ 次： 选择一个包含有一个元素的下标 $i$，然后用 $i$ 调用函数 $f$，函数 $f$ 定义如下：  注意如果 $a[i] = 0$，那我们认为下标 $i$ 不包含一个元素。 在所有操作后，剩下的 $2 ^ g - 1$ 个元素需要位于下标在 $1$ 到 $2 ^ g - 1$ 中的位置。现在 Drazil 想要知道，剩下的 $2 ^ g - 1$ 个数之和最小可能是多少。请计算这个最小的和，并找到一个能够达到最小值的操作序列。 ### 输入格式 第一行输入一个整数 $t ~ (1 \le t \le 70\ 000)$，表示测试数据组数。 对于每组测试数据，输入两行。 第一行输入两个整数 $h, g ~ (1 \le g \lt h \le 20)$。 第二行输入 $n = 2 ^ h - 1$ 个两两不同的正整数 $a[1], a[2], \ldots a[n] ~ (1 \le a[i] \lt 2 ^ {20})$。对于所有 $i ~(2 \le i \le 2 ^ h - 1)~$，$a[i] \lt a\left[ \left\lfloor \frac{i}{2} \right\rfloor \right]$。 每组测试数据的 $n$ 之和不超过 $2 ^ {20}$。 ### 输出格式 对于每组测试数据，输出两行。 第一行输出一个整数，表示使得堆的高度降低到 $g$ 后堆中元素之和的最小值。 第二行输出 $2 ^ h - 2 ^ g$ 个整数 $v_1, v_2, \ldots, v_{2 ^ h - 2 ^ g}$，表示在第 $i$ 步操作中调用了函数 $f(v_i)$。

题目描述

Drazil likes heap very much. So he created a problem with heap: There is a max heap with a height $ h $ implemented on the array. The details of this heap are the following: This heap contains exactly $ 2^h - 1 $ distinct positive non-zero integers. All integers are distinct. These numbers are stored in the array $ a $ indexed from $ 1 $ to $ 2^h-1 $ . For any $ 1 < i < 2^h $ , $ a[i] < a[\left \lfloor{\frac{i}{2}}\right \rfloor] $ . Now we want to reduce the height of this heap such that the height becomes $ g $ with exactly $ 2^g-1 $ numbers in heap. To reduce the height, we should perform the following action $ 2^h-2^g $ times: Choose an index $ i $ , which contains an element and call the following function $ f $ in index $ i $ :  Note that we suppose that if $ a[i]=0 $ , then index $ i $ don't contain an element. After all operations, the remaining $ 2^g-1 $ element must be located in indices from $ 1 $ to $ 2^g-1 $ . Now Drazil wonders what's the minimum possible sum of the remaining $ 2^g-1 $ elements. Please find this sum and find a sequence of the function calls to achieve this value.

输入输出格式

输入格式

The first line of the input contains an integer $ t $ ( $ 1 \leq t \leq 70\,000 $ ): the number of test cases. Each test case contain two lines. The first line contains two integers $ h $ and $ g $ ( $ 1 \leq g < h \leq 20 $ ). The second line contains $ n = 2^h-1 $ distinct positive integers $ a[1], a[2], \ldots, a[n] $ ( $ 1 \leq a[i] < 2^{20} $ ). For all $ i $ from $ 2 $ to $ 2^h - 1 $ , $ a[i] < a[\left \lfloor{\frac{i}{2}}\right \rfloor] $ . The total sum of $ n $ is less than $ 2^{20} $ .

输出格式

For each test case, print two lines. The first line should contain one integer denoting the minimum sum after reducing the height of heap to $ g $ . The second line should contain $ 2^h - 2^g $ integers $ v_1, v_2, \ldots, v_{2^h-2^g} $ . In $ i $ -th operation $ f(v_i) $ should be called.

输入输出样例

输入样例 #1

2
3 2
7 6 3 5 4 2 1
3 2
7 6 5 4 3 2 1

输出样例 #1

10
3 2 3 1
8
2 1 3 1

题意翻译

### 题目描述 Drazil 非常喜欢堆这个数据结构。因此他造了一段关于堆的题目： 有一个高度为 $h$ 的大根堆存储在数组内。具体情况如下： 这个堆中有恰好 $2 ^ h - 1$ 个正整数，这些正整数两两不同。这些数存储在数组 $a$ 内下标 $1$ 到 $2 ^ h - 1$ 的位置。对于任意的 $1 \lt i \lt 2 ^ h$，都有 $a[i] \lt a\left[ \left\lfloor \frac{i}{2} \right\rfloor \right]$。 现在我们想要减小这个堆的高度到 $g$，使得堆中恰好只有 $2 ^ g - 1$ 个数。为了减小高度，我们需要进行下述操作 $2 ^ h - 2 ^ g$ 次： 选择一个包含有一个元素的下标 $i$，然后用 $i$ 调用函数 $f$，函数 $f$ 定义如下：  注意如果 $a[i] = 0$，那我们认为下标 $i$ 不包含一个元素。 在所有操作后，剩下的 $2 ^ g - 1$ 个元素需要位于下标在 $1$ 到 $2 ^ g - 1$ 中的位置。现在 Drazil 想要知道，剩下的 $2 ^ g - 1$ 个数之和最小可能是多少。请计算这个最小的和，并找到一个能够达到最小值的操作序列。 ### 输入格式 第一行输入一个整数 $t ~ (1 \le t \le 70\ 000)$，表示测试数据组数。 对于每组测试数据，输入两行。 第一行输入两个整数 $h, g ~ (1 \le g \lt h \le 20)$。 第二行输入 $n = 2 ^ h - 1$ 个两两不同的正整数 $a[1], a[2], \ldots a[n] ~ (1 \le a[i] \lt 2 ^ {20})$。对于所有 $i ~(2 \le i \le 2 ^ h - 1)~$，$a[i] \lt a\left[ \left\lfloor \frac{i}{2} \right\rfloor \right]$。 每组测试数据的 $n$ 之和不超过 $2 ^ {20}$。 ### 输出格式 对于每组测试数据，输出两行。 第一行输出一个整数，表示使得堆的高度降低到 $g$ 后堆中元素之和的最小值。 第二行输出 $2 ^ h - 2 ^ g$ 个整数 $v_1, v_2, \ldots, v_{2 ^ h - 2 ^ g}$，表示在第 $i$ 步操作中调用了函数 $f(v_i)$。