链接
难度：\(\texttt{1656}\)
\(n\) 个点 \(m\) 条无向边，每条边 \((u_i,v_i)\) 有一个对应的时间 \(t_i\)。
\(q\) 次询问，每次询问从 \(x_i\) 只经过 \(t_i>y_i\) 的边共能到达多少个点。
数据范围：\(1\le n,q\le 100000, 0\le m\le 200000,1\le u_i\not v_i\le n,1\le t_i,y_i\le 100000\)。
第一眼什么神仙题，第二眼什么垃圾题。
发现只有 \(t_i>y_i\) 的边才会对本次询问产生影响，考虑对加边和询问离线处理，按时间从大至小用并查集维护连通块大小。
注意因为是 \(t_i>y_i\)，同一时间询问需放在合并之前。
# include <bits/stdc++.h>
using namespace std;
const int N = 100000, Q = 100000, M = 200000;
int fa [N + 10], siz [N + 10];
int getfa (int x) {
if (fa [x] ^ x) {
return fa [x] = getfa (fa [x]);
}
return x;
}
void merge (int x, int y) {
x = getfa (x), y = getfa (y);
if (x ^ y) {
if (siz [x] > siz [y]) {
x ^= y ^= x ^= y;
}
fa [x] = y;
siz [y] += siz [x];// 维护连通块大小
}
return ;
}
struct opt {
int y, a, b, id;
} qu [M + Q + 10];
int ans [Q + 10];
int main () {
ios :: sync_with_stdio (false);
cin .tie (0);
cout .tie (0);
int n;
cin >> n;
for (int i = 1; i <= n; ++ i) {
fa [i] = i, siz [i] = 1;
}
int m;
cin >> m;
for (int i = 1, a, b, y; i <= m; ++ i) {
cin >> a >> b >> y;
qu [i] = {y, a, b, 0};
}
int q;
cin >> q;
for (int i = 1, a, y; i <= q; ++ i) {
cin >> a >> y;
qu [m + i] = {y, a, 0, i};
}// 离线处理
sort (qu + 1, qu + m + q + 1, [] (opt a, opt b) {
if (a .y ^ b .y) {
return a .y > b .y;
}
return a .id > b .id;// 同一时间询问在前
});
for (int i = 1; i <= m + q; ++ i) {
if (qu [i] .id) {
ans [qu [i] .id] = siz [getfa (qu [i] .a)];
}
else {
merge (qu [i] .a, qu [i] .b);
}
}
for (int i = 1; i <= q; ++ i) {
cout << ans [i] << '\n';
}
return 0;
}