Tác giả:
Reviewer:
Note: Để hiểu được bài viết này, các bạn cần có kiến thức về:
Cho một đồ thị đỉnh, và hiện tại thì chưa có cạnh nào. Có truy vấn, mỗi truy vấn có dạng biểu thị rằng
Sau mỗi truy vấn, hãy in ra số thành phần liên thông trong đồ thị hiện tại.
Nếu làm như bình thường (thêm/xóa cạnh rồi sau mỗi truy vấn lại BFS/DFS), thì đpt là .
Để có thể giải quyết bài toán với giới hạn như trên, ta có cách làm duới đây:
Định nghĩa việc một cạnh xuất hiện sau "thời điểm " là việc cạnh này đang ở trong đồ thị sau truy vấn thứ .
Xem xét ví dụ với bộ dữ liệu như sau
5 10
1 1 2
1 1 3
1 1 4
1 2 5
2 1 2
1 4 5
1 1 2
2 1 4
2 2 5
2 1 2
Dưới đây là Segment Tree khi ta thêm cạnh các khoảng thời gian và (Những đỉnh ta thêm cạnh được tô màu xanh lá cây)
struct edge
{
int u, v;
edge() {}
edge(int _u, int _v) : u(_u), v(_v) {}
};
// những cạnh được update
int answer[MAXQ];
vector<edge> nw_edges[MAXQ << 2];
// root[x] là gốc của thành phần liên thông chứa đỉnh x
// sz[x] là số đỉnh trong thành phần liên thông với gốc là đỉnh x
int sz[MAXN], root[MAXN];
// với mỗi lần cập nhật, ta lưu lại đỉnh được thay đổi size hoặc root để lúc sau cập nhật lại
// lưu ý rằng ta không cần lưu root cũ vì root cũ cảu một đỉnh trước khi merge là chính nó
struct update
{
int node, old_size;
update() {}
update(int _node, int _old_size) : node(_node), old_size(_old_size) {}
};
stack<update> rollback;
int total_rollback[MAXQ << 2]; // với mỗi đỉnh trong segment tree, ta lưu số lần cập nhật để lúc sau có thể rollback
int rt(int x)
{ // ta không dùng path compression và chấp nhận đpt O(log2(n)) cho mỗi lần tìm root
return (x == root[x] ? x : rt(root[x]));
}
// lưu lại số tplt hiện tại
int cur_comp;
void merge(int id, int x, int y)
{ // chúng ta merge như bình thường
x = rt(x);
y = rt(y);
if(x == y) return;
if (sz[x] < sz[y])
swap(x, y);
// lưu lại size cũ của các đỉnh để rollback lại
rollback.push({x, sz[x]});
rollback.push({y, sz[y]});
total_rollback[id] += 2;
sz[x] += sz[y];
root[y] = x;
}
// cập nhật một cạnh tồn tại trong khoảng (l, r)
void upd(int id, int l, int r, int L, int R, edge cur_edge)
{
if (l > R || r < L)
return;
if (l >= L && r <= R)
{
nw_edges[id].push_back(cur_edge);
return;
}
int mid = (l + r) >> 1;
upd(id << 1, l, mid, L, R, cur_edge);
upd(id << 1 | 1, mid + 1, r, L, R, cur_edge);
}
void get_ans(int id, int l, int r)
{
// giả sử ta đang ở đoạn (l, r)
// thêm vào những cạnh được lưu trong đỉnh này
// ngoài ra lưu những node thay đổi root và size trong DSU
for (auto e : nw_edges[id])
{
merge(id, e.u, e.v);
}
// mỗi lần merge chúng ta cộng total_rollback[id] lên 2
cur_comp -= ((int)total_rollback[id] >> 1);
if (l == r)
{
answer[l] = cur_comp; // đáp án cho query thứ l là số component hiện tại
// lưu đáp án
}
// đi xuống các node con
else{
int mid = (l + r) >> 1;
get_ans(id << 1, l, mid);
get_ans(id << 1 | 1, mid + 1, r);
}
// update lại đáp án
cur_comp += ((int)total_rollback[id] >> 1);
// xóa đi những cạnh vừa được thêm vào theo thứ tự ngược lại.
// lưu ý rằng sau khi ra khỏi node hiện tại thì ta
// quay về trạng thái trước khi vào node
while (total_rollback[id])
{
int node = rollback.top().node, old_size = rollback.top().old_size;
rollback.pop();
root[node] = node;
sz[node] = old_size;
total_rollback[id]--;
}
}
Bằng cách làm như trên
Về mặt thời gian:
Về mặt không gian: , đây chính là tổng số cạnh chúng ta thêm vào các vector