P15583 [KTSC 2026] Communication Network 2 / Communication Network 2

Note: You can get more sample tests in the attachments.

There is an undirected graph with $N$ vertices, numbered $0 \sim N-1$. There are no self-loops in this graph. Initially, the graph has no edges. You are given $T$ edge sets $E_0,\ldots,E_{T-1}$. For $u=0,1,\cdots,T-1$, at time $u+0.5$, take the XOR (symmetric difference) of $E_u$ and the current edge set of the graph. In other words, let the current edge set be $E$, and for every $e\in E_u$: - If $e$ is in $E$, delete $e$ from $E$. - Otherwise, add $e$ to $E$. For a non-negative integer $t$ and two vertices $a,b$, we say that $a,b$ are **connected at time $\boldsymbol{t}$** if and only if at time $t$ there exists a path connecting $a$ and $b$. In particular, if $a=b$, then by definition this statement is always true for any $t$. Furthermore, for integers $0\le l\le r\le T$ and two vertices $a,b$, we say that $a,b$ are **connected during the time interval $\boldsymbol{[l,r]}$** if and only if $a,b$ are connected at every time $t=l,l+1,\ldots,r$. There are $Q$ queries. Each query gives $x,l,r$. Return the number of vertices $y$ such that $x,y$ are connected during the time interval $[l,r]$ ($0\le x\le N-1$, $0\le l\le r\le T$, $0\le y\le N-1$). ### Implementation Details **This is a functional interactive problem**. You do not need to, and should not, implement the `main` function. You should implement the following function: ```cpp vector count_computers(int N, int T, int Q, vector E, vector F) ``` - $E$: an array storing the edge sets. The size of $E$ is $T$. Each $E[i]$ is a non-empty edge array representing the set $E_i$. Each edge is given as an array of size $2$, with elements $[a,b]$ in order, representing an edge connecting vertices $a$ and $b$. - $F$: an array storing the queries. The size of $F$ is $Q$. For any $0\le i\le Q-1$, $F[i]$ represents the $i$-th query. Each query is given as an array of size $3$, with elements $[x,l,r]$ in order, where $x$ is a vertex and $[l,r]$ is a time interval. - Return an array $R$ of size $Q$. For any $0\le j\le Q-1$, $R[j]$ is the answer to the $j$-th query. - This function is called exactly once. Your source code must not call any input/output functions.

The input format of the sample grader program is as follows. $|E_i|$ denotes the size of the set $E_i$, and $S = \sum_{0 \le i \le T-1} |E_i|$. * Line $1$: $N$ $T$ $Q$. * For all $0 \le i \le T-1$: * Line $2 + \sum_{0 \le j < i} (1 + |E_j|)$: $|E_i|$. * Line $2 + \sum_{0 \le j < i} (1 + |E_j|) + k$ ($0 \le k < |E_i| - 1$): $a \ b$ (the two endpoints of the $k$-th edge in $E_i$). * Line $2 + S + T + i$ ($0 \le i \le Q - 1$): $x \ l \ r$ (each element of $F[i]$).

The sample grader program outputs the answers in the following format: * Line $1 + i$ ($0 \le i \le Q - 1$): $R[i]$.

### Constraints - $2\le N\le 100\, 000$. - $1\le T\le 100\, 000$. - $1\le Q\le 250\, 000$. - $E_i$ is an edge set, and all edges inside it are pairwise distinct. - Let $S=\sum_{0\le i\lt T-1} |E_i|$, then $S\le 100\, 000$. - For every edge $[a,b]$ given in the input, $0\le a\lt b\le N-1$. - For every query given in the input, $0\le x\le N-1,0\le l\le r\le T$. ### Subtasks | ID | Score | Limit | | :-: | :-: | :- | | $1$ | $5 $ | $N,S,Q\le 100$ | | $2$ | $12$ | $N,S,Q\le 5\, 000$ | | $3$ | $19$ | For all queries, $l=r$ | | $4$ | $23$ | For all edges $[a,b]$ given in $E$, $\vert a-b\vert =1$ | | $5$ | $41$ | No additional constraints | ### Sample Consider the following call. ``` 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]]]) ``` There are $4$ vertices in the graph. At each time, the graph is as follows: * At time $0$: $0$ edges. * At time $1$: $2$ edges: $(0, 1), (1, 2)$. * At time $2$: $4$ edges: $(0, 1), (1, 2), (2, 3), (1, 3)$. * At time $3$: $4$ edges: $(1, 2), (2, 3), (1, 3), (0, 3)$. * At time $4$: $2$ edges: $(0, 1), (1, 3)$. * At time $5$: $1$ edge: $(0, 1)$. A total of $7$ queries are given: * Query $0$: At time $1$, vertex $1$ is connected to the set $\{0, 1, 2\}$. * Query $1$: At time $2$, vertex $2$ is connected to the set $\{0, 1, 2, 3\}$. * Query $2$: At time $3$, vertex $3$ is connected to the set $\{0, 1, 2, 3\}$. * Query $3$: Since there are no edges at time $0$, from time $0$ to $5$, vertex $0$ is only connected to vertex $0$. * Query $4$: From time $1$ to $3$, vertex $2$ is connected to the set $\{0, 1, 2\}$. * Query $5$: From time $1$ to $4$, vertex $1$ is connected to the set $\{0, 1\}$. * Query $6$: From time $2$ to $3$, vertex $3$ is connected to the set $\{0, 1, 2, 3\}$. Therefore, the function should return $[3, 4, 4, 1, 3, 2, 4]$. You can get more sample tests in the attachments. Translated by ChatGPT 5