P16665 [CSPro 25] 通信系统管理

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：。

你负责管理一个计算机通信系统。 有 $n$ 台计算机接入了该系统，编号为 $1 \sim n$，它们之间可以互相发送数据。 由于设备条件限制，机器之间不能任意多地发送数据。每两台机器之间均有一个“每日可用额度”的限制，单位为 MB/day，表示这两台机器每日可以互相发送的数据量（双方各自向对方发送的数据量之和）的最大值。 最初，任意两台机器的每日可用额度均为 $0$。为了能发送数据，机器管理者需要向你申请额度。每个申请形如 $u\ v\ x\ y$ 的格式，表示机器 $u$ 和 $v$ 的每日可用额度增大 $x$ MB/day，持续 $y$ 天（即从申请当天开始至申请后第 $y - 1$ 天内有效，从第 $y$ 天开始失效）。不同申请的效果是可以叠加的。 定义每台机器的“通信主要对象”为当前时刻与该机器的每日可用额度最大的机器（如果有并列，则取其中编号最小的机器）；如果一台机器与任何机器的每日可用额度均为 $0$，则称其为“通信孤岛”，并认为其没有“通信主要对象”；如果两台机器 $x$ 和 $y$ 互为“通信主要对象”，则称它们是一个“通信对”。 每天开始时，你都会先接受若干个额度申请，你需要依次处理这些申请；而后，你将接收到若干个查询某台机器的“通信主要对象”的请求；最后，你可能还希望求出此时的“通信孤岛”和“通信对”各有多少。 请你编写一段程序来实现上述任务。

从标准输入读入数据。 第一行：2 个正整数 $n, m$，表示机器数和天数。 接下来 $3m$ 行，每两行描述一天中的事件，格式如下： - 第 1 行：首先是一个非负整数 $k_i$，表示当天额度申请的数量。接下来有 $4k_i$ 个非负整数，依次描述每一个额度申请，格式如题面中所述。 - 第 2 行：首先是一个非负整数 $l_i$，表示当天查询“通信主要对象”的数量。接下来有 $l_i$ 个正整数，依次表示查询的机器编号，保证编号在 $[1, n]$ 范围内。 - 第 3 行：2 个整数 $p_i, q_i$，取值均为 $0$ 或 $1$，分别表示当天是否要查询“通信孤岛”和“通信对”的数量。其中 $p_i = 1$ 表示需要查询“通信孤岛”的数量，$p_i = 0$ 表示不需要查询；$q_i$ 的含义同理。

输出到标准输出。 对于每个查询分别输出一行，一个非负整数表示该查询的答案。 查询按照天数顺序输出，对于同一天内的查询，先按照输入顺序输出所有查询“通信主要对象”的答案，再依次输出查询“通信孤岛”和“通信对”的答案（如果当天需要查询的话）。 如果某台被查询“通信主要对象”的机器是“通信孤岛”，认为查询结果为 $0$。

### 子任务 设 $A = \sum_{i=1}^{m} k_i$，$B = \sum_{i=1}^{m} l_i$。 - 子任务 1（20 分）：满足 $n, m \leq 1000$，$A, B \leq 2000$； - 子任务 2（10 分）：满足 $p_i = q_i = 0$； - 子任务 3（10 分）：满足 $l_i = q_i = 0$； - 子任务 4（15 分）：满足 $l_i = 0$； - 子任务 5（10 分）：满足 $k_1 = A$，对于所有额度申请均满足 $y = m$； - 子任务 6（15 分）：满足 对于所有额度申请均满足 $y = m$； - 子任务 7（20 分）：无特殊性质。 对于 100% 的数据，$1 \leq n, m \leq 10^5$，$1 \leq A, B \leq 2 \times 10^5$，$1 \leq u, v \leq n$，$1 \leq x \leq 10^9$，$1 \leq y \leq m$。 所有额度申请均满足 $u \neq v$。