Bảo trì mạng
Đề bài
Mô tả
Trung tâm dữ liệu của công ty Nhật Minh có máy chủ được đánh số từ đến . Máy chủ thứ có hiệu năng là số nguyên dương .
Các máy chủ được nối với nhau bằng những sợi cáp mạng. Ban đầu chưa có sợi cáp nào. Hai máy chủ được gọi là thuộc cùng một cụm nếu có thể truyền dữ liệu giữa chúng qua một hoặc nhiều sợi cáp liên tiếp; một máy chủ luôn thuộc cùng cụm với chính nó.
Trong một đợt bảo trì, kỹ thuật viên thực hiện lần lượt thao tác theo thứ tự thời gian. Mỗi thao tác thuộc một trong bốn loại sau:
1 u v: cắm thêm một sợi cáp nối máy chủ và máy chủ ;2 u v: rút một sợi cáp đang nối máy chủ và máy chủ ;3 u x: thay máy chủ bằng máy mới có hiệu năng ;4 u: truy vấn: cho biết cụm chứa máy chủ hiện có bao nhiêu máy chủ và hiệu năng lớn nhất trong cụm đó là bao nhiêu.
Lưu ý:
- Giữa hai máy chủ có thể có nhiều sợi cáp cùng lúc. Khi rút cáp, chỉ một sợi bị rút, các sợi còn lại giữa cặp máy đó vẫn hoạt động.
- Thao tác thay máy chủ không làm thay đổi các sợi cáp đang nối vào máy đó.
- Dữ liệu bảo đảm mỗi thao tác dạng
2 u vchỉ xuất hiện khi đang có ít nhất một sợi cáp nối và , và bảo đảm có ít nhất một thao tác loại .
Hãy trả lời tất cả các thao tác loại .
Dữ liệu vào
- Dòng đầu chứa hai số nguyên và .
- Dòng thứ hai chứa số nguyên .
- Mỗi dòng trong dòng tiếp theo mô tả một thao tác theo một trong bốn dạng nêu trên.
Dữ liệu ra
Với mỗi thao tác loại , theo đúng thứ tự xuất hiện, ghi ra một dòng chứa hai số nguyên cách nhau bởi dấu cách: số lượng máy chủ trong cụm chứa và hiệu năng lớn nhất trong cụm đó.
Ràng buộc
- ; .
- .
- , đối với thao tác loại và ; đối với thao tác loại .
Subtasks
- Subtask 1 ( số điểm): .
- Subtask 2 ( số điểm): không có thao tác loại .
- Subtask 3 ( số điểm): không có thao tác loại .
- Subtask 4 ( số điểm): .
- Subtask 5 ( số điểm): không có ràng buộc gì thêm.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 9 4 9 2 7 5 1 1 2 4 1 1 2 3 4 3 3 3 20 4 1 2 1 2 4 1 4 3 |
2 9 3 9 3 20 1 4 2 20 |
Sau khi cắm cáp , cụm chứa máy gồm : có máy, hiệu năng lớn nhất là . Cắm thêm cáp , cụm trở thành : có máy, hiệu năng lớn nhất vẫn là . Thay máy bằng máy có hiệu năng : cụm vẫn gồm máy nhưng hiệu năng lớn nhất trở thành . Rút cáp : cụm chứa máy chỉ còn với hiệu năng ; còn cụm chứa máy là với hiệu năng lớn nhất . |
| 4 13 3 8 5 1 1 1 2 1 1 2 1 2 3 4 3 2 2 1 4 1 3 2 4 4 3 2 1 2 4 1 4 2 1 3 4 4 4 |
3 8 3 8 3 5 1 3 2 5 3 5 |
Ví dụ bổ sung. Giữa máy và máy có hai sợi cáp. Thao tác 2 2 1 chỉ rút một sợi, sợi còn lại vẫn nối với , nên cụm chứa máy vẫn là với hiệu năng lớn nhất . Thay máy bằng máy có hiệu năng : hiệu năng lớn nhất của cụm còn . Rút nốt sợi cáp : cụm chứa máy chỉ còn (hiệu năng ), cụm chứa máy là (hiệu năng lớn nhất ). Cuối cùng cắm cáp : cụm chứa máy là , hiệu năng lớn nhất . |
Bình luận