#P18911. [2026多校联测]存储空间
[2026多校联测]存储空间
存储空间
题目描述
给定一棵有根有序满二叉树,根为节点 ,共有 个叶子和 个节点。每个非叶子节点恰有一个左孩子和一个右孩子。
按照先访问左子树、再访问右子树的顺序,将所有叶子从左到右编号为 。叶子编号与输入中的节点编号不同。
每个节点 对应其子树中叶子编号形成的区间 ,并有正整数费用 。本文中 表示整数集合 。
维护一个初始为空的区间集合 ,其中每个元素都是 的非空子区间。
一个存储方案是节点集合 。若对于每个 ,都存在一个子集 ,使得 两两不交且其并集恰为 ,则称该方案可行。方案的费用为
给定 次操作:
+ l r:将区间 加入 ,保证此前不存在;- l r:从 删除区间 ,保证此前存在。
每次操作后,求可行方案的最小费用,以及达到最小费用的方案数。方案数对 取模。
两个方案不同,当且仅当它们选择的节点集合不同。同一个节点集合对目标区间的不同覆盖方式不会重复计数。
注意, 可以同时包含祖先和后代;两两不交的要求只作用于覆盖某个目标区间时选出的 。不同目标区间的覆盖可以复用同一个已选节点。
输入格式
第一行包含两个整数 。
接下来 行,第 行包含三个整数 ,分别表示节点 的左孩子编号、右孩子编号和费用。
叶子节点满足 ;非叶子节点的两个孩子编号均属于 。节点编号不保证满足父亲先于孩子。
接下来 行,每行以字符 + 或 - 开头,随后为两个整数 ,描述一次操作。这里 是叶子编号。
输出格式
输出 行,每行两个整数,分别为本次操作后的最小费用和最优方案数对 取模的结果。
最小费用不取模,并且可能超过 位有符号整数的范围。
样例 1
输入
2 6
2 3 2
0 0 1
0 0 1
+ 1 2
+ 1 1
+ 2 2
- 1 1
- 1 2
- 2 2
输出
2 2
2 1
2 1
2 1
1 1
0 1
样例解释
根对应区间 ,费用为 ;两个叶子的费用均为 。
第一次操作后,可以选根,也可以选两个叶子,最小费用为 ,共有两种方案。第二次操作后,选择根还需要额外选择左叶子,因此最优方案只剩下两个叶子。
第三、四次操作后的最优方案仍是两个叶子。第五次操作后只需选择右叶子。最后集合为空,唯一的最优方案是空集,费用为 。
数据范围与子任务
对于所有数据:
- ,;
- ,;
- 给定结构是以 为根、所有节点均可达、恰有 个叶子的有序满二叉树;
- ;
- 所有插入、删除操作均合法。
根的深度定义为 。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 5 | , |
| 2 | 10 | |
| 3 | 对每个非叶子节点,令 ,其左右子树区间恰为 与 | |
| 4 | 5 | 所有叶子的深度不超过 |
| 5 | 10 | 所有操作中的区间均等于某个节点对应的区间 |
| 6 | 每个非叶子节点的左孩子都是叶子 | |
| 7 | 每个非叶子节点的右子树叶子数不少于左子树叶子数 | |
| 8 | 只有插入操作 | |
| 9 | 5 | 所有操作的区间长度至多为 |
| 10 | 25 | 无 |
各子任务独立计分,需通过该子任务的全部测试点才能获得相应分数。更多样例见附加文件 samples.zip。