QOJ.ac

QOJ

Time Limit: 2.5 s Memory Limit: 512 MB Total points: 100 Hackable ✓
[+5]

# 8226. 堆操作练习题2

Statistics

给定一个大小恰好为 2h1 的大根堆, 节点编号依次为 12h1i 号节点的父亲为 i/2i 号结点的权值恰好为 ai,保证 ai 为正数且互不相同。

你可以对这个堆进行若干次操作,每一次操作会给定一个下标 i(1i<2h)。你需要保证执行的该操作时候 ai0。每一次操作具体内容如下:

  • 执行 ai=0
  • 执行如下操作, 直到 2i2h:
    • 如果 a2i<a2i+1, 则交换 aia2i+1 的值, 之后执行 i=2i+1
    • 否则交换 aia2i 的值, 之后执行 i=2i
  • 换而言之,你可以理解为将堆中元素 ai 置为 0 后, 从节点 i 开始模拟的一次 SiftDown 过程, 使得其仍然满足大根堆性质。

给定一个集合 S{1,2,,2h1}, 你需要执行上述操作若干次,使得经过上述操作后满足对于任意 iS, ai0 。在满足上述要求的前提下, 你希望最小化 2h1i=1ai 的值。你只需要输出最小值即可。

---- 题目来源:北京大学2023年秋季学期 《数据结构与算法A(实验班)》期末上机测试 Problem 4


小 Z 在复习期末考试题目的时候看到了这道题。作为熟练的竞赛选手小 Z 很快发现了这道题目的关键性质:在满足对于任意 iS, ai0 的前提下,最小化 2h1i=1ai 的值最终操作结果(也就是经过若干次操作的堆)唯一!,并迅速解决掉了这道题目。

在解决这道题目之后,小 Z 觉得这题还能够继续加强,于是给出了如下的修改版本:

给定集合 S1,S2{1,2,,2h1}, 初始 S1=S2=。你需要支持如下询问:

  • 1 x y(y{1,2},1x<2h): Sy=Sy{x}. 保证 xSy,保证操作后 S1S2=
  • 2 x y(y{1,2},1x<2h): Sy=Sy{x}. 保证 xSy,保证操作后 S1S2=
  • 3 x z(1x<2h,1z106): 对于所有 S1S(S1S2), 询问有多少个不同的 S,使得存在一种操作方案,满足如下性质:
    • A. 经过上述操作后满足对于任意 iS, ai0
    • B. 在满足条件 A 的情况下,2h1i=1ai 最小。这里我们不加证明的给出:在满足条件 A 的情况下,最小化 2h1i=1ai 的值的最终操作结果(也就是经过若干次操作的堆)唯一!
    • C. 在满足条件 B 的情况下,经过上述操作后,满足 ax=z

输入格式

第一行一个正整数 h 表示堆的大小。

第二行,一行 2h1 个数字,第 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%): h2,Q50

Subtask 2(10%): h4,Q500

Subtask 3(20%): h9,Q5000, 保证对于操作 1,2, y=1

Subtask 4(20%): h9,Q5000

Subtask 5(20%): 保证对于操作 1,2, y=1

Subtask 6(20%): 无特殊性质。

对于所有测试数据,满足: 1h18,1Q5×105,1ai106