Hướng giải của Dòng Thời Gian Kết Nối

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Lời Giải: Dòng Thời Gian Kết Nối

Ý tưởng: Offline Segment Tree + DSU Rollback

Quan sát: Mỗi cạnh \((u,v)\) tồn tại trong một khoảng \([l, r]\) (thêm ở thời điểm \(l\), xóa ở \(r+1\)).

Thuật toán:

  1. Đọc offline toàn bộ \(Q\) sự kiện, xác định khoảng \([l,r]\) của mỗi cạnh.
  2. Dùng Segment Tree trên thời gian: thêm cạnh vào tất cả các node bao phủ \([l,r]\).
  3. DFS trên segment tree + DSU Rollback:
    • Khi vào node: gộp các cạnh của node vào DSU.
    • Khi đến lá \(i\): nếu sự kiện \(i\) là truy vấn 3 u v, trả lời từ DSU hiện tại.
    • Khi ra node: rollback DSU về trạng thái trước.
// Segment tree DFS
void dfs(int node, int lo, int hi, DSU& d, vector<tuple<int,int,int>>& queries) {
    int save = d.save();
    for (auto [u, v] : seg[node]) d.unite(u, v);
    if (lo == hi) {
        auto [t, u, v] = queries[lo];
        if (t == 3) puts(d.same(u,v) ? "YES" : "NO");
    } else {
        int mid = (lo+hi)/2;
        dfs(2*node, lo, mid, d, queries);
        dfs(2*node+1, mid+1, hi, d, queries);
    }
    d.restore(save);
}

Độ phức tạp

\(O(Q \log^2 N)\).

Nhận xét

Không có ý kiến tại thời điểm này.