#P14072. [KTSC 2026 R1]通信网络 2

    ID: 13281 传统题 6000ms 1024MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>CF3300NOI/NOI+/CTS线段树分治可撤销并查集按大小合并缩点离散化最长公共前缀线段树上二分离线查询扫描线树状数组

[KTSC 2026 R1]通信网络 2

题目描述

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

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

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

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

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

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

  • 给定计算机 xx 和时间区间 [l,r][l, r],请返回满足“计算机 xx 与 yy 在 ll 秒到 rr 秒期间连通”的 yy 的个数。其中 0≤x≤N−10 \leq x \leq N-1;0≤l≤r≤T0 \leq l \leq r \leq T;0≤y≤N−10 \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)
  • NN:计算机的数量。
  • TT:时间步数。
  • QQ:查询的数量。
  • EE:表示添加或移除线路集合的数组。EE 的大小为 TT。每个 E[i]E[i] 是一个由一条或多条不同线路组成的数组,代表集合 EiE_i。每条线路以大小为 22 的数组 [a,b][a, b] 形式给出,表示该线路连接计算机 aa 和 bb。
  • FF:表示查询的数组。FF 的大小为 QQ。对于所有 ii (0≤i≤Q−1)(0 \leq i \leq Q-1),F[i]F[i] 表示第 ii 个查询。查询以大小为 33 的数组 [x,l,r][x, l, r] 给出,其中 xx 代表计算机编号,l,rl, r 代表时间区间。
  • 该函数应返回一个大小为 QQ 的整数数组 RR。对于所有 jj (0≤j≤Q−1)(0 \leq j \leq Q-1),R[j]R[j] 存储第 jj 个查询的答案。
  • 该函数仅会被调用一次。

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

样例

考虑如下调用:

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}})

网络中有 44 台计算机。 各秒时,网络的线路构成如下:

  • 00 秒:线路 00 条。
  • 11 秒:线路 22 条:(0,1),(1,2)(0,1), (1,2)。
  • 22 秒:线路 44 条:(0,1),(1,2),(2,3),(1,3)(0,1), (1,2), (2,3), (1,3)。
  • 33 秒:线路 44 条:(1,2),(2,3),(1,3),(0,3)(1,2), (2,3), (1,3), (0,3)。
  • 44 秒:线路 22 条:(0,1),(1,3)(0,1), (1,3)。
  • 55 秒:线路 11 条:(0,1)(0,1)。

共给出 77 个查询:

  • 查询 00:计算机 11 在 11 秒时与计算机 {0,1,2}\{0, 1, 2\} 连通。
  • 查询 11:计算机 22 在 22 秒时与计算机 {0,1,2,3}\{0, 1, 2, 3\} 连通。
  • 查询 22:计算机 33 在 33 秒时与计算机 {0,1,2,3}\{0, 1, 2, 3\} 连通。
  • 查询 33:由于 00 秒时没有任何线路存在,计算机 00 从 00 秒到 55 秒期间仅与计算机 {0}\{0\} 连通。
  • 查询 44:计算机 22 从 11 秒到 33 秒期间与计算机 {0,1,2}\{0, 1, 2\} 连通。
  • 查询 55:计算机 11 从 11 秒到 44 秒期间与计算机 {0,1}\{0, 1\} 连通。
  • 查询 66:计算机 33 从 22 秒到 33 秒期间与计算机 {0,1,2,3}\{0, 1, 2, 3\} 连通。

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

数据范围与提示

对于所有输入数据,满足:

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

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

子任务 分值 附加限制
11 55 N,S,Q≤100N, S, Q \leq 100
22 1212 N,S,Q≤5000N, S, Q \leq 5000
33 1919 对于所有查询,满足 l=rl=r
44 2323 对于 EE 中包含的所有线路 [a,b][a, b],满足 $
55 4141 无附加限制

示例评测程序

示例评测程序的输入格式如下。∣Ei∣|E_i| 表示集合 EiE_i 的大小,S=∑0≤j≤T−1∣Ej∣S = \sum_{0 \leq j \leq T-1} |E_j|。

  • 第 11 行:N T QN \ T \ Q
  • 对于所有 0≤i≤T−10 \leq i \leq T-1:
    • 第 2+∑0≤j<i2 + \sum_{0 \leq j < i} (1+∣Ej∣)(1 + |E_j|) 行:∣Ei∣|E_i|
    • 第 2+∑0≤j<i2 + \sum_{0 \leq j < i} (1+∣Ej∣)+k+1(1 + |E_j|) + k + 1 行(0≤k≤∣Ei∣−10 \leq k \leq |E_i|-1):a ba \ b(EiE_i 中第 kk 条边的两端点)
  • 接下来的 QQ 行(0≤i≤Q−10 \leq i \leq Q-1):x l rx \ l \ r(F[i]F[i] 的各元素)

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

  • 第 1+i1+i 行(0≤i≤Q−10 \leq i \leq Q-1):R[i]R[i]