Tóm tắt đề bài

Cho một đồ thị vô hướng gồm \(N\) đỉnh, ban đầu không có cạnh nào. Cần xử lý \(Q\) thao tác thuộc các loại:

• add u v: Thêm cạnh vô hướng giữa hai đỉnh \(u\) và \(v\).
• remove u v: Xóa cạnh vô hướng giữa hai đỉnh \(u\) và \(v\).
• query: Kiểm tra đồ thị hiện tại có phải là đồ thị hai phía (bipartite graph) hay không.

Phân tích

• Điều kiện: \(1 \leq N, Q \leq 10^5\).
• Tính chất đồ thị hai phía: Một đồ thị là hai phía khi và chỉ khi nó không chứa chu trình có độ dài lẻ.
• Thao tác thêm cạnh và kiểm tra tính hai phía có thể thực hiện hiệu quả bằng Disjoint Set Union (DSU). Tuy nhiên, thao tác xóa cạnh trực tiếp trên DSU là rất khó và tốn kém nếu không xử lý offline.

Cách làm đơn giản (Brute Force)

Ý tưởng

• Lưu trữ danh sách kề hoặc tập các cạnh hiện có trong đồ thị.
• Với mỗi thao tác add hoặc remove, ta cập nhật trực tiếp vào danh sách kề.
• Với mỗi thao tác query, ta chạy thuật toán BFS hoặc DFS để tô 2 màu cho đồ thị:
  • Bắt đầu từ mỗi đỉnh chưa được thăm, gán màu \(0\).
  • Thăm các đỉnh kề và gán màu đối nghịch (\(1 - \text{color}\)).
  • Nếu gặp một cạnh nối giữa hai đỉnh có cùng màu, đồ thị chứa chu trình lẻ \(\rightarrow\) không phải hai phía.

Độ phức tạp

• Thời gian: Mỗi thao tác query mất \(O(N + M)\) với \(M\) là số cạnh hiện tại (\(M \leq Q\)). Tổng thời gian là \(O(Q \cdot (N + Q))\).
• Bộ nhớ: \(O(N + Q)\) để lưu danh sách kề.
• Đánh giá: Chỉ phù hợp khi \(N, Q \leq 2000\). Với \(N, Q = 10^5\), thuật toán sẽ bị quá thời gian (Time Limit Exceeded).

Hướng giải quyết (Tối ưu)

Nhận xét

1. Khoảng thời gian tồn tại của cạnh:

   • Mỗi cạnh được thêm vào tại thời điểm \(t_1\) và bị xóa đi tại thời điểm \(t_2\) sẽ tồn tại trong đoạn thời gian \([t_1, t_2 - 1]\). Nếu cạnh không bao giờ bị xóa, nó tồn tại trong \([t_1, Q]\).
   • Bài toán chuyển về: Duy trì đồ thị với các cạnh xuất hiện trong các đoạn thời gian \([L, R]\). Đây là mô hình kinh điển giải bằng Segment Tree over Time kết hợp DSU có khả năng quay lui (Rollback DSU).

2. Kiểm tra tính hai phía bằng DSU mở rộng (2-SAT / DSU đỉnh kép):

   • Với mỗi đỉnh \(u\), ta tạo thêm đỉnh \(u + N\) đại diện cho phía đối diện của \(u\).
   • Khi thêm cạnh \((u, v)\), ta gộp \(u\) với \(v + N\) và gộp \(v\) với \(u + N\).
   • Nếu tại bất kỳ thời điểm nào \(\text{find}(u) = \text{find}(u + N)\), xuất hiện chu trình lẻ và đồ thị không còn là hai phía.
   • Cần sử dụng kỹ thuật Union by Size/Rank (không dùng nén đường đi - path compression) để có thể rollback các thao tác hợp nhất về trạng thái trước đó trong \(O(1)\) mỗi bước.

Thuật toán

1. Tiền xử lý thời gian:
   • Dùng bảng băm (map / dict) lưu lại thời điểm mỗi cạnh \((u, v)\) xuất hiện.
   • Khi gặp thao tác remove u v, xác định khoảng \([L, R] = [\text{start\_time}, \text{current\_time} - 1]\) và thêm cạnh vào cây phân đoạn (Segment Tree).
   • Kết thúc \(Q\) thao tác, những cạnh chưa bị xóa sẽ có khoảng \([L, R] = [\text{start\_time}, Q]\).
2. Cây phân đoạn theo thời gian (Segment Tree over Time):
   • Đoạn \([1, Q]\) được quản lý bởi Segment Tree.
   • Mỗi cạnh có đoạn tồn tại \([L, R]\) sẽ được chèn vào \(O(\log Q)\) nút tương ứng trên cây.
3. Duyệt DFS và Rollback DSU:
   • Duyệt cây từ gốc theo thứ tự tiền thứ tự (DFS):
     • Khi đến một nút, ta lần lượt gộp các cạnh được lưu tại nút đó vào DSU.
     • Ghi lại số phép gộp đã thực hiện để rollback sau này.
     • Nếu đỉnh \(u\) và \(u + N\) cùng thành phần liên thông, ta ghi nhận trạng thái đồ thị bị hỏng tính hai phía.
     • Khi đến nút lá \(t\): Nếu thao tác \(t\) là query, kiểm tra cờ tính hai phía và in kết quả YES hoặc NO.
     • Khi hoàn thành duyệt cả hai cây con, ta hoàn tác (rollback) toàn bộ các phép gộp đã thực hiện tại nút hiện tại và khôi phục cờ tính hai phía.

Độ phức tạp

• Thời gian:
  • Mỗi cạnh được thêm vào \(O(\log Q)\) nút trên Segment Tree.
  • Thao tác trên DSU Rollback (chỉ dùng Union by Size) mất \(O(\log N)\) cho mỗi phép hợp nhất.
  • Tổng độ phức tạp thời gian: \(O(Q \log Q \log N)\).
• Bộ nhớ: \(O(N + Q \log Q)\) để lưu các nút Segment Tree và DSU.