题目描述

通信网络由 $N$ 台计算机和若干连接线路组成。计算机的编号为 $0$ 到 $N-1$。每条线路允许两台不同的计算机进行双向通信。也就是说，通信网络是一个具有 $N$ 个顶点的无向图，每条线路充当连接两个不同顶点的边。初始状态下，网络中不存在任何线路。

每一秒，网络中都会添加或移除若干线路。具体来说，对于每个 $u=0, 1, 2, \dots, T-1$，都会给出一组不同的线路集合 $E_u$。在 $u+0.5$ 秒时，网络中的线路将按以下规则更新：

• 如果 $E_u$ 中的某条线路原本不存在于当前网络中，则将其添加到网络中。
• 如果 $E_u$ 中的某条线路原本已存在于当前网络中，则将其从网络中移除。

对于任意整数 $t$ 和两台计算机 $a, b$，若计算机 $a$ 和 $b$ 在 $t$ 秒时是连通的，是指仅使用 $t$ 秒时网络中存在的线路，即可找到一条连接计算机 $a$ 和 $b$ 的路径。当 $a=b$ 时，无论网络的线路构成如何，这一条件始终成立。

进一步地，对于任意整数 $0 \leq l \leq r \leq T$ 和两台计算机 $a, b$，若计算机 $a$ 和 $b$ 在 $l$ 秒到 $r$ 秒期间是连通的，是指对于所有 $t=l, l+1, \dots, r$，计算机 $a$ 和 $b$ 在 $t$ 秒时均保持连通。

为了研究在特定的时间区间内，某台计算机能否稳定地与其他计算机进行通信，请你回答如下 $Q$ 个查询：

• 给定计算机 $x$ 和时间区间 $[l, r]$，请返回满足“计算机 $x$ 与 $y$ 在 $l$ 秒到 $r$ 秒期间连通”的 $y$ 的个数。其中 $0 \leq x \leq N-1$；$0 \leq l \leq r \leq T$；$0 \leq y \leq N-1$。

实现细节

你需要实现以下函数：

vector<int> count_computers(int N, int T, int Q, vector<vector<array<int, 2>>> E, vector<array<int, 3>> F)

• $N$：计算机的数量。
• $T$：时间步数。
• $Q$：查询的数量。
• $E$：表示添加或移除线路集合的数组。$E$ 的大小为 $T$。每个 $E[i]$ 是一个由一条或多条不同线路组成的数组，代表集合 $E_i$。每条线路以大小为 $2$ 的数组 $[a, b]$ 形式给出，表示该线路连接计算机 $a$ 和 $b$。
• $F$：表示查询的数组。$F$ 的大小为 $Q$。对于所有 $i$ $(0 \leq i \leq Q-1)$，$F[i]$ 表示第 $i$ 个查询。查询以大小为 $3$ 的数组 $[x, l, r]$ 给出，其中 $x$ 代表计算机编号，$l, r$ 代表时间区间。
• 该函数应返回一个大小为 $Q$ 的整数数组 $R$。对于所有 $j$ $(0 \leq j \leq Q-1)$，$R[j]$ 存储第 $j$ 个查询的答案。
• 该函数仅会被调用一次。

在提交的源代码中，你不应在任何地方执行输入或输出函数。

样例

考虑如下调用：

count_computers(4, 5, 7, {{{0, 1}, {1, 2}}, {{2, 3}, {1, 3}}, {{0, 1}, {0, 3}}, 
{{0, 1}, {1, 2}, {0, 3}, {2, 3}}, {{1, 3}}}, {{1, 1, 1}, {2, 2, 2}, {3, 3, 3}, 
{0, 0, 5}, {2, 1, 3}, {1, 1, 4}, {3, 2, 3}})

网络中有 $4$ 台计算机。 各秒时，网络的线路构成如下：

• $0$ 秒：线路 $0$ 条。
• $1$ 秒：线路 $2$ 条：$(0,1), (1,2)$。
• $2$ 秒：线路 $4$ 条：$(0,1), (1,2), (2,3), (1,3)$。
• $3$ 秒：线路 $4$ 条：$(1,2), (2,3), (1,3), (0,3)$。
• $4$ 秒：线路 $2$ 条：$(0,1), (1,3)$。
• $5$ 秒：线路 $1$ 条：$(0,1)$。

共给出 $7$ 个查询：

• 查询 $0$：计算机 $1$ 在 $1$ 秒时与计算机 $\{0, 1, 2\}$ 连通。
• 查询 $1$：计算机 $2$ 在 $2$ 秒时与计算机 $\{0, 1, 2, 3\}$ 连通。
• 查询 $2$：计算机 $3$ 在 $3$ 秒时与计算机 $\{0, 1, 2, 3\}$ 连通。
• 查询 $3$：由于 $0$ 秒时没有任何线路存在，计算机 $0$ 从 $0$ 秒到 $5$ 秒期间仅与计算机 $\{0\}$ 连通。
• 查询 $4$：计算机 $2$ 从 $1$ 秒到 $3$ 秒期间与计算机 $\{0, 1, 2\}$ 连通。
• 查询 $5$：计算机 $1$ 从 $1$ 秒到 $4$ 秒期间与计算机 $\{0, 1\}$ 连通。
• 查询 $6$：计算机 $3$ 从 $2$ 秒到 $3$ 秒期间与计算机 $\{0, 1, 2, 3\}$ 连通。

因此，函数应返回 $[3, 4, 4, 1, 3, 2, 4]$。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 100000$
• $1 \leq T \leq 100000$
• $1 \leq Q \leq 250000$
• $E_i$ 由互不相同的线路组成。
• 设 $S$ 为所有 $E_i$ $(0 \leq i \leq T-1)$ 的大小之和，则 $S \leq 100000$。
• 对于输入中给出的所有线路，满足 $0 \leq a < b \leq N-1$。
• 对于输入中给出的所有查询，满足 $0 \leq x \leq N-1, 0 \leq l \leq r \leq T$。

详细子任务附加限制及分值如下表所示。

示例评测程序

示例评测程序的输入格式如下。$|E_i|$ 表示集合 $E_i$ 的大小，$S = \sum_{0 \leq j \leq T-1} |E_j|$。

• 第 $1$ 行：$N \ T \ Q$
• 对于所有 $0 \leq i \leq T-1$：
  • 第 $2 + \sum_{0 \leq j < i}$ $(1 + |E_j|)$ 行：$|E_i|$
  • 第 $2 + \sum_{0 \leq j < i}$ $(1 + |E_j|) + k + 1$ 行（$0 \leq k \leq |E_i|-1$）：$a \ b$（$E_i$ 中第 $k$ 条边的两端点）
• 接下来的 $Q$ 行（$0 \leq i \leq Q-1$）：$x \ l \ r$（$F[i]$ 的各元素）

示例评测程序按以下格式输出答案：

• 第 $1+i$ 行（$0 \leq i \leq Q-1$）：$R[i]$