算法
(分块) $O(Q\sqrt{M})$
首先开三个数组 big
,memo
,以及 last
big[i]
表示点 $i$ 的度数是否大于等于 $D$
memo
用来维护两个信息,即点 $i$ 上一次的更新时间和它的点权
last[i]
表示点 $i$ 上一次的更新时间
其次若某个点 $v$ 的度数大于等于 $D$,考察和它直接相连的点 $u$,若点 $u$ 的度数不足 $D$,则断开它与 $v$ 的连接,即去掉 $v \to u$ 这条有向边。
注意到,显然每个点是由和他直接相连的点来更新
若待询问的点 $v$ 的度数大于等于 $D$,直接更新和它相连的点 $u$ 的点权,同时更新点 $v$ 的 memo
信息
若待询问的点 $v$ 的度数不足 $D$,此时若存在和点 $v$ 相连的点 $u$ 满足”它的度数大于等于 $D$ 且它的上一次更新时间大于点 $v$ 的 last
值”这一条件,则更新点 $v$ 的点权和 last
值,然后用点 $v$ 的点权来更新和它直接相连的点 $w$ 的点权,若点 $w$ 的度数不足 $D$,则更新它的 last
值。
为了达到根号平衡,$D$ 应该取 $\sqrt{2M}$,大概取到 $600$ 即可。
C++ 代码
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using P = std::pair<int, int>;
int main() {
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> to(n);
rep(i, m) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
to[b].push_back(a);
}
const int D = 600;
vector<P> memo(n, P(-1, -1));
vector<int> last(n, -1);
vector<int> x(n);
vector<bool> big(n);
rep(i, n) big[i] = to[i].size() >= D;
rep(i, n) if (big[i]) {
vector<int> nto;
for (int j : to[i]) {
if (big[j]) nto.push_back(j);
}
to[i] = nto;
}
rep(i, n) x[i] = i + 1;
auto get = [&](int v) {
for (int u : to[v]) {
if (big[u] and memo[u].first > last[v]) {
last[v] = memo[u].first;
x[v] = memo[u].second;
}
}
};
rep(qi, q) {
int v;
cin >> v;
--v;
if (big[v]) {
for (int u : to[v]) x[u] = x[v];
memo[v] = P(qi, x[v]);
}
else {
get(v);
for (int u : to[v]) {
x[u] = x[v];
if (!big[u]) last[u] = qi;
}
}
}
rep(i, n) {
if (!big[i]) get(i);
cout << x[i] << " ";
}
return 0;
}