Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] DSU có hoàn tác đếm thành phần

    Quản lý nnn phần tử (ban đầu mỗi phần tử là một thành phần riêng). Xử lý qqq thao tác:

    • 1 u v: hợp nhất thành phần chứa uuu và vvv.
    • 2: hoàn tác thao tác hợp nhất gần nhất (kể cả khi nó không thay đổi gì).
    • 3: in số thành phần liên thông hiện tại.

    Dùng DSU theo hạng (rank) không nén đường để hỗ trợ hoàn tác.

    • Định dạng đầu vào:

      Dòng đầu: nnn, qqq. qqq dòng thao tác như mô tả.

    • Ràng buộc đầu vào:

      1≤n≤2⋅1051 \le n \le 2\cdot10^51≤n≤2⋅105, 1≤q≤4⋅1051 \le q \le 4\cdot10^51≤q≤4⋅105, mỗi 2 luôn có thao tác hợp nhất trước đó chưa bị hoàn tác.

    • Định dạng đầu ra:

      Mỗi thao tác loại 3 in số thành phần trên một dòng.

    Ví dụ:

    Đầu vào:

    4 6
3
1 1 2
3
1 3 4
2
3

    Đầu ra:

    4
3
3

    Giải thích:

    Đầu 4 thành phần. Hợp 1-2 → 3. Hợp 3-4 → 2, nhưng bị hoàn tác → trở lại 3.

    Đang tải editor...