trang chủ / đề bài / tddn26_netmain

Bảo trì mạng

Đề bài

Mô tả

Trung tâm dữ liệu của công ty Nhật Minh có N máy chủ được đánh số từ 1 đến N. Máy chủ thứ i có hiệu năng là số nguyên dương ai.

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 Q 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ủ u và máy chủ v;
  • 2 u v: rút một sợi cáp đang nối máy chủ u và máy chủ v;
  • 3 u x: thay máy chủ u bằng máy mới có hiệu năng x;
  • 4 u: truy vấn: cho biết cụm chứa máy chủ u 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 v chỉ xuất hiện khi đang có ít nhất một sợi cáp nối u và v, và bảo đảm có ít nhất một thao tác loại 4.

Hãy trả lời tất cả các thao tác loại 4.

Dữ liệu vào

  • Dòng đầu chứa hai số nguyên N và Q.
  • Dòng thứ hai chứa N số nguyên a1,a2,…,aN.
  • Mỗi dòng trong Q 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 4, 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 u và hiệu năng lớn nhất trong cụm đó.

Ràng buộc

  • 2≤N≤2·105; 1≤Q≤2·105.
  • 1≤ai≤109.
  • 1≤u,v≤N, u≠v đối với thao tác loại 1 và 2; 1≤x≤109 đối với thao tác loại 3.

Subtasks

  • Subtask 1 (15% số điểm): N,Q≤2000.
  • Subtask 2 (20% số điểm): không có thao tác loại 2.
  • Subtask 3 (20% số điểm): không có thao tác loại 3.
  • Subtask 4 (15% số điểm): N,Q≤5·104.
  • Subtask 5 (30% 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 1−2, cụm chứa máy 1 gồm {1,2}: có 2 máy, hiệu năng lớn nhất là max(4,9)=9. Cắm thêm cáp 2−3, cụm trở thành {1,2,3}: có 3 máy, hiệu năng lớn nhất vẫn là 9. Thay máy 3 bằng máy có hiệu năng 20: cụm vẫn gồm 3 máy nhưng hiệu năng lớn nhất trở thành 20. Rút cáp 1−2: cụm chứa máy 1 chỉ còn {1} với hiệu năng 4; còn cụm chứa máy 3 là {2,3} với hiệu năng lớn nhất 20.
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 1 và máy 2 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 1 với 2, nên cụm chứa máy 1 vẫn là {1,2,3} với hiệu năng lớn nhất 8. Thay máy 2 bằng máy có hiệu năng 4: hiệu năng lớn nhất của cụm còn max(3,4,5)=5. Rút nốt sợi cáp 1−2: cụm chứa máy 1 chỉ còn {1} (hiệu năng 3), cụm chứa máy 2 là {2,3} (hiệu năng lớn nhất 5). Cuối cùng cắm cáp 3−4: cụm chứa máy 4 là {2,3,4}, hiệu năng lớn nhất 5.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0