P15583 [KTSC 2026] 通信网络 2 / Communication Network 2

注意：本题你可在附件中获取更多样例。

有一张 $N$ 个点的无向图，其中点编号 $0\sim N-1$。这张图中不会出现自环。起初，这张图中没有边。 给定 $T$ 个边集 $E_0,\ldots,E_{T-1}$。对于 $u=0,1,\cdots,T-1$，在时刻 $u+0.5$，将 $E_u$ 与这张图此时的边集作「异或」（对称差）。换言之，设此时图的边集为 $E$，然后对任意 $e\in E_u$： - 若 $e$ 在 $E$ 中，从 $E$ 中删去 $e$； - 否则，将 $e$ 添加到 $E$ 中。 对于非负整数 $t$ 和两个点 $a,b$，我们称点 $a,b$ **在时刻 $\boldsymbol{t}$ 连通**，当且仅当时刻 $t$ 时存在一条连通点 $a,b$ 的路径。特别地，若 $a=b$，由定义可知上述命题对任意 $t$ 恒为真。 更进一步地，对于整数 $0\le l\le r\le T$ 和两个点 $a,b$，我们称点 $a,b$ **在时段 $\boldsymbol{[l,r]}$ 连通**，当且仅当点 $a,b$ 在时刻 $t=l,l+1,\ldots,r$ 时均连通。 有 $Q$ 个询问，每个询问给定 $x,l,r$，返回满足点 $x,y$ 在时段 $[l,r]$ 连通的 $y$ 的数量（$0\le x\le N-1$，$0\le l\le r\le T$，$0\le y\le N-1$）。 ### 实现细节 **这是一道函数式交互题**。你不必，也不应实现 `main` 函数。 你应当实现以下的函数： ```cpp vector count_computers(int N, int T, int Q, vector E, vector F) ``` - $E$：存储边集的数组。$E$ 的大小为 $T$。每个 $E[i]$ 为一个非空的边数组，表示集合 $E_i$。每条边以大小为 $2$ 的数组的形式给出，其中的元素依次为 $[a,b]$，表示一条连接点 $a,b$ 的边。 - $F$：存储询问的数组。$F$ 的大小为 $Q$。对于任意 $0\le i\le Q-1$，$F[i]$ 表示第 $i$ 次询问。每个询问以大小为 $3$ 的形式给出，其中元素依次为 $[x,l,r]$，其中 $x$ 为一个点，$[l,r]$ 为一个时段。 - 返回一个大小为 $Q$ 的数组 $R$。对于任意 $0\le j\le Q-1$，$R[j]$ 表示第 $j$ 次询问的答案。 - 该函数被调用恰好一次。 你的源代码中不应调用任何输入/输出函数。

示例评测程序的输入格式如下。$|E_i|$ 表示集合 $E_i$ 的大小，且 $S = \sum_{0 \le i \le T-1} |E_i|$。 * 第 $1$ 行：$N$ $T$ $Q$ * 对于所有 $0 \le i \le T-1$： * 第 $2 + \sum_{0 \le j < i} (1 + |E_j|)$ 行：$|E_i|$ * 第 $2 + \sum_{0 \le j < i} (1 + |E_j|) + k$ 行（$0 \le k < |E_i| - 1$）：$a \ b$（$E_i$ 中第 $k$ 条边的两个端点） * 第 $2 + S + T + i$ 行（$0 \le i \le Q - 1$）：$x \ l \ r$（$F[i]$ 的每个元素）

示例评测程序按以下格式输出答案： * 第 $1 + i$ 行（$0 \le i \le Q - 1$）：$R[i]$

### 数据范围 - $2\le N\le 100\, 000$； - $1\le T\le 100\, 000$； - $1\le Q\le 250\, 000$； - $E_i$ 是边集，其中边两两不同。 - 令 $S=\sum_{0\le i\lt T-1} |E_i|$，则 $S\le 100\, 000$； - 对于输入中给出的边 $[a,b]$，有 $0\le a\lt b\le N-1$； - 对于输入中给出的查询，有 $0\le x\le N-1,0\le l\le r\le T$。 ### 子任务 | 编号 | 得分 | 限制 | | :-: | :-: | :- | | $1$ | $5 $ | $N,S,Q\le 100$ | | $2$ | $12$ | $N,S,Q\le 5\, 000$ | | $3$ | $19$ | 对于所有查询，$l=r$ | | $4$ | $23$ | 对于 $E$ 中给出的所有边 $[a,b]$，$\vert a-b\vert =1$ | | $5$ | $41$ | 无额外限制 | ### 样例 考虑以下调用。 ``` 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], [2, 2], [3, 3], [0, 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$ 到 $5$，点 $0$ 仅与点 $0$ 相连。 * 查询 $4$：从时刻 $1$ 到 $3$，点 $2$ 与点集 $\{0, 1, 2\}$ 相连。 * 查询 $5$：从时刻 $1$ 到 $4$，点 $1$ 与点集 $\{0, 1\}$ 相连。 * 查询 $6$：从时刻 $2$ 到 $3$，点 $3$ 与点集 $\{0, 1, 2, 3\}$ 相连。 因此，函数应返回 $[3, 4, 4, 1, 3, 2, 4]$。 可在附件中获取更多样例。