Description
给定一张 (n) 个点，(m) 条边的无向图，边 (i) 的权值为 (d_i)。现有 (q) 次操作，第 (j) 个操作有两种模式：
- (1 b_j r_j)：将第 (b_j) 条边的权改为 (r_j)。
- (2 s_j w_j)：询问与点 (s_j) 连通的点的数量（包括自己）。若边 ((u, v)) 的权值 (d ge w_j)，那么视作 (u, v) 连通。若 ((a, b), (b, c)) 分别连通，那么 ((a, c)) 也连通。
对于每个 (2) 操作输出答案。
Hint
- (1le nle 5 imes 10^4)
- (0le mle 10^5)
- (1le qle 10^5)
- (d, r, win [1, 10^9])
Solution
先看一个比较显然的部分分做法：将询问离线，按 (w) 排序，边按 (d) 排序，降序。如果没有询问那这个就是 naive，而正好有这档部分分。考虑修改：将边按是否有修改分类，无修直接加，带修在处理询问时暴力枚举，根据操作的时间做修改，然后一个个加入并查集，最后撤回。由于需要可撤销，需要启发式合并。复杂度 (O(qlog q + mlog m + q^2log n))。数据分治期望有 (27) pts。
一次性枚举所有询问，这就是复杂度瓶颈所在。但如果直接暴力就得扫一遍所有边。
基于上述解法，考虑根号平衡的思想来优化——对询问分块！
设块长为 (s)。对于当前块，我们默认前面块已经处理好修改操作了，那么就不需要再考虑前面的块的修改。首先任然是两次排序，一次所有边，一次 块内的询问，那么复杂度是 (O(mlog m + slog s))。枚举询问时，对于所有无修边，直接加入；对于带修边，由分了块，带修边不会太多，我们直接枚举，把有效的边插入，统计答案后再撤销即可，这里复杂度为 (O(s^2log s))。
当前块处理完后，清空询问与修改。这样的算法总复杂度为 (O(s(s^2log s + slog s + mlog m)) = O(s^3log s + smlog m))。
当 (s = sqrt{q}) 是，复杂度为 (O(qsqrt{q}log q + msqrt{q} log m))。
实现细节较多，需要注意。
Code
/*
* Author : _Wallace_
* Source : https://www.cnblogs.com/-Wallace-/
* Problem : LOJ#3145 APIO2019 桥梁
*/
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
const int N = 5e4 + 5;
const int M = 1e5 + 5;
int n, m, q;
struct Edge {
int u, v, w, idx;
} e[M];
struct Command {
int pos, val, idx;
}; vector<Command> Q, E;
int ans[M];
int fa[N], siz[N], stk[N], top = 0;
int find(int x) {
return x == fa[x] ? x : find(fa[x]);
}
void merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (siz[x] < siz[y]) swap(x, y);
stk[++top] = y;
siz[x] += siz[y], fa[y] = x;
}
void backtrack(int time) {
while (top > time) {
int x = stk[top--];
siz[fa[x]] -= siz[x];
fa[x] = x;
}
}
void reset() {
for (int i = 1; i <= n; i++)
fa[i] = i, siz[i] = 1;
top = 0;
}
int cur[M];
int ref[M];
void solve() {
sort(e + 1, e + 1 + m, [](const Edge& a, const Edge& b) {
return a.w > b.w;
});
sort(Q.begin(), Q.end(), [](const Command& a, const Command& b) {
return a.val > b.val;
});
for (int i = 1; i <= m; i++)
ref[e[i].idx] = i;
reset();
vector<Command> E_tmp;
for (auto t : E) {
cur[t.pos] = -1;
E_tmp.push_back(Command{t.pos, e[ref[t.pos]].w, 0});
}
for (auto t : E) E_tmp.push_back(t);
for (int i = 0, j = 1; i < int(Q.size()); i++) {
for (; j <= m && e[j].w >= Q[i].val; j++)
if (!cur[e[j].idx]) merge(e[j].u, e[j].v);
for (auto t : E_tmp) if (t.idx <= Q[i].idx)
cur[t.pos] = t.val;
int bt = top; // backtrack
for (auto t : E) if (cur[t.pos] >= Q[i].val)
merge(e[ref[t.pos]].u, e[ref[t.pos]].v);
ans[Q[i].idx] = siz[find(Q[i].pos)];
backtrack(bt);
}
for (auto t : E) e[ref[t.pos]].w = t.val, cur[t.pos] = 0;
E.clear(), Q.clear();
}
signed main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> e[i].u >> e[i].v >> e[i].w;
e[i].idx = i;
}
cin >> q;
int gap = int(sqrt(q)) << 2;
for (int i = 1; i <= q; i++) {
int op, pos, val;
cin >> op >> pos >> val;
if (op == 1) E.push_back(Command{pos, val, i});
else Q.push_back(Command{pos, val, i});
if (i % gap == 0) solve();
}
if (q % gap != 0) solve();
for (int i = 1; i <= q; i++)
if (ans[i]) printf("%d
", ans[i]);
return 0;
}