시간 제한메모리 제한제출정답맞힌 사람정답 비율
6 초 2048 MB29229.091%

문제

통신망은 $N$개의 컴퓨터와 회선으로 구성된다. 컴퓨터는 $0$번부터 $N-1$번까지 번호가 붙어 있다. 하나의 회선은 서로 다른 $2$개의 컴퓨터가 양방향으로 통신할 수 있도록 한다. 즉, 통신망은 $N$개의 정점을 가지는 무방향 그래프이며, 각 회선은 서로 다른 두 정점을 잇는 간선의 역할을 한다. 초기 통신망에는 어떠한 회선도 존재하지 않는다.

매 초마다 통신망에는 여러 회선들이 추가되거나 제거된다. 구체적으로, 매 $u = 0, 1, 2, \cdots , T-1$에 대해서, 서로 다른 회선들의 집합 $E_u$가 주어진다. $u+0.5$초에, 통신망에 있는 회선들은 다음과 같은 규칙으로 갱신된다:

  • 만약 $E_u$에 존재하는 회선이 기존 통신망에 존재하지 않았다면, 이 회선을 통신망에 추가한다.
  • 만약 $E_u$에 존재하는 회선이 기존 통신망에 존재한다면, 이 회선을 통신망에서 제거한다.

어떠한 정수 $t$와 두 컴퓨터 $a$, $b$에 대해서, 컴퓨터 $a$와 $b$가 $t$초에 연결되어 있다는 것은, $t$초에 통신망에 존재하는 회선들만 사용해서 컴퓨터 $a$와 컴퓨터 $b$를 잇는 경로가 존재함을 뜻한다. $a=b$일 경우, 이는 통신망의 회선 구성과 상관없이 항상 참임을 알 수 있다.

더 나아가, 어떠한 정수 $0 \le l \le r \le T$와 두 컴퓨터 $a$, $b$에 대해 컴퓨터 $a$와 $b$가 $l$초부터 $r$초까지 연결되어 있다는 것은, 모든 $t = l, l+1, \cdots , r$에 대해 컴퓨터 $a$와 $b$가 $t$초에 연결되어 있음을 뜻한다.

특정 시간 구간 동안 어떠한 컴퓨터에서 안정적으로 다른 컴퓨터와 통신할 수 있는지를 연구하기 위해, 당신은 다음과 같은 $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$)

함수 목록 및 정의

다음 함수를 구현해야 한다.

vector<int> count_computers(int N, int T, int Q, vector<vector<array<int, 2>>> E, vector<array<int, 3>> F)
  • $E$: 추가되거나 제거되는 회선들의 집합을 나타내는 배열. $E$의 크기는 $T$이다. 각 $E[i]$는 $1$개 이상의 서로 다른 회선들로 이루어진 배열이며, 집합 $E_i$를 뜻한다. 각 회선은 크기 $2$의 배열로 주어지며, 배열의 각 원소는 순서대로 $[a,b]$이다. 이는 회선이 컴퓨터 $a$와 $b$를 연결함을 뜻한다.
  • $F$: 질문들을 나타내는 배열. $F$의 크기는 $Q$이다. 모든 $i$ ($0 \le i \le Q - 1$)에 대해, $F[i]$는 $i$번 질문을 표현한다. 질문은 크기 $3$의 배열로 주어진다. 배열의 원소는 순서대로 $[x,l,r]$이다. 이때, $x$는 컴퓨터를 나타내며, $l$, $r$은 시간 구간을 나타낸다.
  • 이 함수는 크기가 $q$인 정수 배열 $r$를 반환해야 한다. 모든 $j$ ($0 \le j \le q - 1$)에 대해, $R[j]$는 $j$번 질문의 정답을 저장한다.
  • 이 함수는 단 한 번만 호출된다.

제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.

제한

  • $2 \le N \le 100\, 000$
  • $1 \le T \le 100\, 000$
  • $1 \le Q \le 250\, 000$
  • $E_i$는 서로 다른 회선들로 이루어져 있다.
  • $S$를 모든 $E_i$ ($0 \le i \le T - 1$)의 크기 합이라 할 때, $S \le 100\,000$
  • 입력으로 주어지는 모든 회선에 대해서, $0 \le a < b \le N - 1$.
  • 입력으로 주어지는 모든 질문에 대해서, $0 \le x \le N - 1$, $0 \le l \le r \le T$.

서브태스크

번호배점제한
15

$N,S,Q ≤ 100$

212

$N,S,Q ≤ 5\, 000$

319

모든 질문에 대해서, $l = r$

423

$E$에 포함되는 모든 회선 $[a,b]$에 대해서, $| a - b | = 1$

541

추가적인 제약조건이 없다.

예제

다음 호출을 생각해보자.

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]$를 반환해야 한다.

샘플 그레이더

샘플 그레이더의 입력 형식은 다음과 같다. $|E_i|$는 집합 $E_i$의 크기를 뜻하며, $S = \sum_{0 \le j \le T - 1}{E_j|}$이다.

  • line $1$: $N$ $T$ $Q$
  • 모든 $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 + 1$ ($0 ≤ k ≤ |E_i| − 1$): $a$ $b$ ($E_i$의 $k$번 간선의 양 끝점)
  • line $2 + S + T + i$ ($0 ≤ i ≤ Q − 1$): $x$ $l$ $r$ ($F[i]$의 각 원소)

샘플 그레이더는 다음 형식으로 답을 출력한다:

  • line $1 + i$ ($0 ≤ i ≤ Q − 1$): $R[i]$

제출할 수 있는 언어

C++17, C++20, C++23, C++26, C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.