#P18911. [2026多校联测]存储空间

[2026多校联测]存储空间

存储空间

题目描述

给定一棵有根有序满二叉树,根为节点 11,共有 nn 个叶子和 N=2n−1N=2n-1 个节点。每个非叶子节点恰有一个左孩子和一个右孩子。

按照先访问左子树、再访问右子树的顺序,将所有叶子从左到右编号为 1,2,…,n1,2,\ldots,n。叶子编号与输入中的节点编号不同。

每个节点 vv 对应其子树中叶子编号形成的区间 Iv=[Lv,Rv]I_v=[L_v,R_v],并有正整数费用 wvw_v。本文中 [l,r][l,r] 表示整数集合 {x∈Z∣l≤x≤r}\{x\in\mathbb Z\mid l\le x\le r\}。

维护一个初始为空的区间集合 T\mathcal T,其中每个元素都是 [1,n][1,n] 的非空子区间。

一个存储方案是节点集合 P\mathcal P。若对于每个 J∈TJ\in\mathcal T,都存在一个子集 U⊆P\mathcal U\subseteq\mathcal P,使得 {Iv∣v∈U}\{I_v\mid v\in\mathcal U\} 两两不交且其并集恰为 JJ,则称该方案可行。方案的费用为

∑v∈Pwv.\sum_{v\in\mathcal P}w_v.

给定 qq 次操作:

  • + l r:将区间 [l,r][l,r] 加入 T\mathcal T,保证此前不存在;
  • - l r:从 T\mathcal T 删除区间 [l,r][l,r],保证此前存在。

每次操作后,求可行方案的最小费用,以及达到最小费用的方案数。方案数对 998244353998244353 取模。

两个方案不同,当且仅当它们选择的节点集合不同。同一个节点集合对目标区间的不同覆盖方式不会重复计数。

注意,P\mathcal P 可以同时包含祖先和后代;两两不交的要求只作用于覆盖某个目标区间时选出的 U\mathcal U。不同目标区间的覆盖可以复用同一个已选节点。

输入格式

第一行包含两个整数 n,qn,q。

接下来 N=2n−1N=2n-1 行,第 vv 行包含三个整数 lsv,rsv,wvls_v,rs_v,w_v,分别表示节点 vv 的左孩子编号、右孩子编号和费用。

叶子节点满足 lsv=rsv=0ls_v=rs_v=0;非叶子节点的两个孩子编号均属于 [1,N][1,N]。节点编号不保证满足父亲先于孩子。

接下来 qq 行,每行以字符 + 或 - 开头,随后为两个整数 l,rl,r,描述一次操作。这里 l,rl,r 是叶子编号。

输出格式

输出 qq 行,每行两个整数,分别为本次操作后的最小费用和最优方案数对 998244353998244353 取模的结果。

最小费用不取模,并且可能超过 3232 位有符号整数的范围。

样例 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,2][1,2],费用为 22;两个叶子的费用均为 11。

第一次操作后,可以选根,也可以选两个叶子,最小费用为 22,共有两种方案。第二次操作后,选择根还需要额外选择左叶子,因此最优方案只剩下两个叶子。

第三、四次操作后的最优方案仍是两个叶子。第五次操作后只需选择右叶子。最后集合为空,唯一的最优方案是空集,费用为 00。

数据范围与子任务

对于所有数据:

  • 1≤n,q≤1051\le n,q\le10^5,N=2n−1N=2n-1;
  • 0≤lsv,rsv≤N0\le ls_v,rs_v\le N,1≤wv≤1091\le w_v\le10^9;
  • 给定结构是以 11 为根、所有节点均可达、恰有 nn 个叶子的有序满二叉树;
  • 1≤l≤r≤n1\le l\le r\le n;
  • 所有插入、删除操作均合法。

根的深度定义为 00。

子任务 分值 附加限制
1 5 n≤7n\le7,q≤100q\le100
2 10 nq≤2×106nq\le2\times10^6
3 对每个非叶子节点,令 m=⌊(Lv+Rv)/2⌋m=\lfloor(L_v+R_v)/2\rfloor,其左右子树区间恰为 [Lv,m][L_v,m] 与 [m+1,Rv][m+1,R_v]
4 5 所有叶子的深度不超过 3030
5 10 所有操作中的区间均等于某个节点对应的区间
6 每个非叶子节点的左孩子都是叶子
7 每个非叶子节点的右子树叶子数不少于左子树叶子数
8 只有插入操作
9 5 所有操作的区间长度至多为 22
10 25 无

各子任务独立计分,需通过该子任务的全部测试点才能获得相应分数。更多样例见附加文件 samples.zip。