Đề bài

Một mạng truyền thông gồm \(N\) máy tính, đánh số từ \(0\) đến \(N-1\), và các đường truyền hai chiều. Ban đầu mạng không có đường truyền nào.

Với mỗi \(u=0,1,\ldots,T-1\), một tập \(E_u\) gồm các đường truyền phân biệt được cho trước. Tại thời điểm \(u+0.5\), trạng thái của từng đường truyền trong \(E_u\) bị đảo: đường chưa có sẽ được thêm, còn đường đang có sẽ bị xóa.

Hai máy \(a,b\) được gọi là kết nối tại giây \(t\) nếu có một đường đi giữa chúng chỉ dùng các đường truyền tồn tại tại giây \(t\). Một máy luôn kết nối với chính nó. Hai máy được gọi là kết nối trong toàn bộ khoảng \([l,r]\) nếu chúng kết nối tại mọi thời điểm nguyên \(t=l,l+1,\ldots,r\).

Có \(Q\) truy vấn. Mỗi truy vấn cho máy \(x\) và khoảng thời gian \([l,r]\); hãy trả về số máy \(y\) kết nối với \(x\) trong toàn bộ khoảng đó.

Yêu cầu cài đặt

Bạn cần cài đặt hàm:

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

• E có độ dài \(T\). Mỗi E[i] là tập các đường truyền bị đảo tại thời điểm \(i+0.5\); mỗi đường truyền được biểu diễn bởi [a, b].
• F có độ dài \(Q\). F[j] = [x, l, r] mô tả truy vấn thứ \(j\).
• Hàm phải trả về mảng \(R\) có độ dài \(Q\), trong đó \(R[j]\) là đáp án truy vấn thứ \(j\).
• Hàm được gọi đúng một lần và chương trình nộp không được thực hiện thao tác vào/ra.

Ràng buộc

• \(2\le N\le 100\,000\).
• \(1\le T\le 100\,000\).
• \(1\le Q\le 250\,000\).
• Mỗi \(E_i\) chứa các đường truyền phân biệt.
• Gọi \(S=\sum_{i=0}^{T-1}|E_i|\), ta có \(S\le 100\,000\).
• Mọi đường truyền thỏa mãn \(0\le a<b\le N-1\).
• Mọi truy vấn thỏa mãn \(0\le x\le N-1\) và \(0\le l\le r\le T\).

Phân nhóm

Grader mẫu

Grader mẫu đọc \(N,T,Q\). Với mỗi \(i\), grader đọc \(|E_i|\) rồi các cặp đầu mút của \(E_i\). Cuối cùng, grader đọc \(Q\) bộ x l r và in từng đáp án trên một dòng.

4 5 7
2
0 1
1 2
2
2 3
1 3
2
0 1
0 3
4
0 1
1 2
0 3
2 3
1
1 3
1 1 1
2 2 2
3 3 3
0 0 5
2 1 3
1 1 4
3 2 3

3
4
4
1
3
2
4

4 5 7
2
0 1
1 2
1
2 3
1
0 1
3
0 1
1 2
2 3
1
1 2
1 1 1
2 2 2
3 3 3
0 0 5
2 1 3
1 1 4
3 2 3

3
4
3
1
2
1
3

5 5 5
5
0 1
0 3
0 2
1 2
0 4
1
1 2
1
0 4
2
0 2
1 2
1
0 3
2 4 5
2 0 0
0 5 5
0 2 5
0 0 3

3
1
3
3
1

10 27 10
1
3 8
1
8 9
1
3 6
1
1 6
1
0 8
1
1 4
1
3 7
1
0 5
1
1 2
1
0 5
1
1 9
1
3 9
1
5 8
1
1 4
1
1 2
1
1 7
1
3 7
1
3 6
1
0 8
1
2 4
1
6 9
1
0 8
1
8 9
1
3 8
1
1 6
1
0 9
1
3 4
5 0 17
8 23 26
5 7 24
4 5 6
0 3 12
8 15 18
2 4 12
6 0 2
5 9 15
1 6 17

1
3
1
1
1
8
1
1
1
6

Nguồn: Kỳ thi tuyển chọn đội tuyển IOI Hàn Quốc 2026 - Vòng 1, giấy phép CC BY-NC-SA 4.0.