U419409 [PKUWC2024] 堆操作练习题 2

北京大学信息学冬季体验营 2024 Day 1 T3

> 给定一个大小恰好为 $2^h−1$ 的大根堆, 节点编号依次为 $1 \sim 2^h−1$。$i$ 号节点的父亲为 $\left\lfloor \dfrac i2 \right\rfloor$。$i$ 号结点的权值恰好为 $a_i$，保证 $a_i$ 为正数且互不相同。 > > 你可以对这个堆进行若干次操作，每一次操作会给定一个下标 $i$（$1 \leq i < 2^h$）。你需要保证执行的该操作时候 $a_i$ 非 $0$。每一次操作具体内容如下： > > - 执行 $a_i=0$。 > - 执行如下操作, 直到 $2i \geq 2^h$： > - 如果 $a_{2i} < a_{2i+1}$，则交换 $a_i$ 和 $a_{2i+1}$ 的值, 之后执行 $i=2i+1$。 > - 否则交换 $a_i$ 和 $a_{2i}$ 的值，之后执行 $i=2i$。 > - 换而言之，你可以理解为将堆中元素 $a_i$ 置为 $0$ 后，从节点 $i$ 开始模拟的一次 SiftDown 过程，使得其仍然满足大根堆性质。 > > 给定一个集合 $S \subseteq \{1,2,\cdots,2^h−1\}$，你需要执行上述操作若干次，使得经过上述操作后满足对于任意 $i \in S$，$a_i \neq 0$。在满足上述要求的前提下, 你希望最小化 $\sum\limits_{i=1}^{2^h−1} a_i$ 的值。你只需要输出最小值即可。 > > ——题目来源：北京大学 2023 年秋季学期 《数据结构与算法 A（实验班）》期末上机测试 Problem 4 小 Z 在复习期末考试题目的时候看到了这道题。作为熟练的竞赛选手小 Z 很快发现了这道题目的关键性质：**在满足对于任意 $i \in S$，$a_i \neq 0$ 的前提下，最小化 $\sum\limits_{i=1}^{2^h−1} a_i$ 的值最终操作结果（也就是经过若干次操作的堆）唯一！** 并迅速解决掉了这道题目。 在解决这道题目之后，小 Z 觉得这题还能够继续加强，于是给出了如下的修改版本： 给定集合 $S_1,S_2 \subseteq \{1,2,\cdots,2^h−1\}$，初始 $S_1=S_2=\varnothing$。你需要支持如下询问： - `1 x y`（$y \in \{1,2\}$，$1 \leq x < 2^h$）：$S_y \gets S_y \cup \{x\}$。保证 $x \not\in S_y$，保证操作后 $S_1 \cap S_2 = \varnothing$。 - `2 x y`（$y \in \{1,2\}$，$1 \leq x < 2^h$）：$S_y \gets S_y - \{x\}$。保证 $x \in S_y$，保证操作后 $S_1 \cap S_2 = \varnothing$。 - `3 x z`（$1 \leq x < 2^h$，$1 \leq z \leq 10^6$）：对于所有 $S_1 \subseteq S \subseteq (S_1 \cup S_2)$，询问有多少个不同的 $S$，使得存在一种操作方案，满足如下性质： - A. 经过上述操作后满足对于任意 $i \in S$，$a_i \neq 0$。 - B. 在满足条件 A 的情况下，$\sum\limits_{i=1}^{2^h−1} a_i$ 最小。这里我们不加证明的给出：**在满足条件 A 的情况下，最小化 $\sum\limits_{i=1}^{2^h−1} a_i$ 的值的最终操作结果（也就是经过若干次操作的堆）唯一！** - C. 在满足条件 B 的情况下，经过上述操作后，满足 $a_x=z$。

第一行一个正整数 $h$ 表示堆的大小。 第二行，一行 $2^h−1$ 个数字，第 $i$ 个数字表示 $a_i$。保证 $a_i$ 互不相同，且满足大根堆性质。 第三行一个正整数 $Q$ 表示询问次数。 接下来 $Q$ 行，一行三个正整数，表示一次询问。

对于所有的询问 $3$，一行一个正整数表示答案。由于答案非常大，你只需要输出其对 $10^9+7$ 取模后的结果即可。

**本题采用捆绑测试。** 对于所有测试数据，保证 $1 \leq h \leq 18$，$1 \leq Q \leq 5 \times 10^5$，$1 \leq a_i \leq 10^6$。 子任务 1（$10$ 分）：保证 $h \leq 2$，$Q \leq 50$。 子任务 2（$10$ 分）：保证 $h \leq 4$，$Q \leq 500$。 子任务 3（$20$ 分）：保证 $h \leq 9$，$Q \leq 5000$，保证对于操作 $1,2$，$y=1$。 子任务 4（$20$ 分）：保证 $h \leq 9$，$Q \leq 5000$。 子任务 5（$20$ 分）：保证对于操作 $1,2$，$y=1$。 子任务 6（$20$ 分）：无特殊性质。