给定一个大小恰好为 2h−1 的大根堆, 节点编号依次为 1∼2h−1。i 号节点的父亲为 ⌊i/2⌋。i 号结点的权值恰好为 ai,保证 ai 为正数且互不相同。你可以对这个堆进行若干次操作,每一次操作会给定一个下标 i(1≤i<2h)。你需要保证执行的该操作时候 ai 非 0。每一次操作具体内容如下:
- 执行 ai=0。
- 执行如下操作, 直到 2i≥2h:
- 如果 a2i<a2i+1, 则交换 ai 和 a2i+1 的值, 之后执行 i=2i+1。
- 否则交换 ai 和 a2i 的值, 之后执行 i=2i。
- 换而言之,你可以理解为将堆中元素 ai 置为 0 后, 从节点 i 开始模拟的一次 SiftDown 过程, 使得其仍然满足大根堆性质。
给定一个集合 S⊆{1,2,⋯,2h−1}, 你需要执行上述操作若干次,使得经过上述操作后满足对于任意 i∈S, ai≠0 。在满足上述要求的前提下, 你希望最小化 2h−1∑i=1ai 的值。你只需要输出最小值即可。
---- 题目来源:北京大学2023年秋季学期 《数据结构与算法A(实验班)》期末上机测试 Problem 4
小 Z 在复习期末考试题目的时候看到了这道题。作为熟练的竞赛选手小 Z 很快发现了这道题目的关键性质:在满足对于任意 i∈S, ai≠0 的前提下,最小化 2h−1∑i=1ai 的值最终操作结果(也就是经过若干次操作的堆)唯一!,并迅速解决掉了这道题目。
在解决这道题目之后,小 Z 觉得这题还能够继续加强,于是给出了如下的修改版本:
给定集合 S1,S2⊆{1,2,⋯,2h−1}, 初始 S1=S2=∅。你需要支持如下询问:
- 1 x y(y∈{1,2},1≤x<2h): Sy=Sy∪{x}. 保证 x∉Sy,保证操作后 S1∩S2=∅。
- 2 x y(y∈{1,2},1≤x<2h): Sy=Sy−{x}. 保证 x∈Sy,保证操作后 S1∩S2=∅。
- 3 x z(1≤x<2h,1≤z≤106): 对于所有 S1⊆S⊆(S1∪S2), 询问有多少个不同的 S,使得存在一种操作方案,满足如下性质:
- A. 经过上述操作后满足对于任意 i∈S, ai≠0。
- B. 在满足条件 A 的情况下,2h−1∑i=1ai 最小。这里我们不加证明的给出:在满足条件 A 的情况下,最小化 2h−1∑i=1ai 的值的最终操作结果(也就是经过若干次操作的堆)唯一!
- C. 在满足条件 B 的情况下,经过上述操作后,满足 ax=z。
输入格式
第一行一个正整数 h 表示堆的大小。
第二行,一行 2h−1 个数字,第 i 个数字表示 ai。保证 ai 互不相同,且满足大根堆性质。
第三行一个正整数 Q 表示询问次数。
接下来 Q 行,一行三个正整数,表示一次询问。
输出格式
对于所有的询问 3,一行一个正整数表示答案。由于答案非常大,你只需要输出其对 1,000,000,007(109+7) 取模后的结果即可。
样例数据
样例输入
2
3 2 1
11
1 1 2
1 2 2
1 3 2
3 1 3
3 1 2
3 1 1
2 1 2
1 1 1
3 1 3
3 1 2
3 1 1
样例输出
4
2
1
2
1
1
子任务
Subtask 1(10%): h≤2,Q≤50。
Subtask 2(10%): h≤4,Q≤500。
Subtask 3(20%): h≤9,Q≤5000, 保证对于操作 1,2, y=1。
Subtask 4(20%): h≤9,Q≤5000
Subtask 5(20%): 保证对于操作 1,2, y=1。
Subtask 6(20%): 无特殊性质。
对于所有测试数据,满足: 1≤h≤18,1≤Q≤5×105,1≤ai≤106。