洛谷P5443 [APIO2019] 桥梁题解

题目链接：P5443 [APIO2019] 桥梁

题意：

圣彼得堡市内所有水路长度总和约 $282$ 千米，市内水域面积占城市面积的 $7\%$。——来自维基百科

圣彼得堡位于由 $m$ 座桥梁连接而成的 $n$ 个岛屿上。岛屿用 $1$ 到 $n$ 的整数编号，桥梁用 $1$ 到 $m$ 的整数编号。每座桥连接两个不同的岛屿。有些桥梁是在彼得大帝时代建造的，其中一些是近期建造的。这导致了不同的桥梁可能有不同的重量限制。更具体地，只有重量不超过 $d_i$ 的汽车才能通过第 $i$ 座桥梁。有时圣彼得堡的一些桥梁会进行翻新，但这并不一定会使桥梁承重变得更好，也就是说，进行翻新的桥梁的 $d_i$ 可能会增加或减少。你准备开发一个产品，用于帮助公民和城市客人。目前，你开发的模块要能执行两种类型的操作：

将桥梁 $b_j$ 的重量限制改为 $r_j$。

统计一辆重为 $w_j$ 的汽车从岛屿 $s_j$ 出发能够到达多少个不同的岛屿。

请你回答所有第二种操作的答案。

输入格式：

第一行包含两个整数 $n$ 和 $m$—— 表示圣彼得堡的岛屿数量与桥梁数量。

接下来 $m$ 行，每行三个整数 $u_i,v_i,d_i$。第 $i$ 行的整数描述了一座连接岛屿 $u_i$ 和 $v_i$，初始时重量限制为 $d_i$ 的桥梁。

接下来一行一个整数 $q$ —— 表示操作的数量。

接下来 $q$ 行按顺序每行描述一个操作。

每行第一个整数 $t_j$ 表示操作类型：

若 $t_j=1$，则该操作是第一种类型，该行接下来给定两个整数 $b_j$ 和 $r_j$，表示桥梁 $b_j$ 的重量限制将变为 $r_j$。

若 $t_j=2$，则该操作是第二种类型，该行接下来给定两个整数 $s_j$ 和 $w_j$，表示一辆重为 $w_j$ 的汽车将要从第 $s_j$ 个岛屿出发。

输出格式：

对于每个第二种类型的询问，输出一行一个整数表示答案。

数据范围：

对于全部数据，$1 \leq n \leq 5\times 10^4$，$0 \leq m \leq 10^5$，$1 \leq q \leq 10^5$。保证 $1 \leq u_i$，$v_i$, $s_j \leq n$，$u_i \neq v_i$，$1 \leq d_i$, $r_j$, $w_j \leq 10^9$，$1 \leq b_j \leq m$，$t_j \in {1,2}$。

考虑没有修改怎么做。那当然是离线以后，把询问按大到小排序，然后用并查集维护边集啦。

那么有修改该怎么做呢？可以想到两种暴力的方式：

对于每次询问直接修改，然后重新用并查集维护一遍，时间复杂度 $\mathcal{O}(Qm)$
对于无修改的边，直接维护。对于有修改的边，暴力枚举，

如果对询问有影响（在询问之前）就临时加入并查集，因此我们需要可撤销并查集

此时的时间复杂度为 $\mathcal{O}(Q\log Q + m \log m + Q^2\log n)$

注意到算法1在边少的时候很快，并且最重要的是把边给改了；算法2在询问少的时候很快。

都说到这了，明摆着就是根号分治嘛。考虑对询问离线后进行分块，记块长为 $S$ 。

每个块内进行暴力2，并在处理完一个块之后把所有块的修改都落实。（~~cxy：怎么感觉这就是在瞎搞啊？~~）

然而此时的复杂度变成了 $\mathcal{O}\left(\frac{Q}{S} m \log m+\frac{Q}{S} S^2 \log n\right)$ ，即 $\mathcal{O}\left(Q S \log n+\frac{Q m \log _2 m}{S}\right)$

取块 $S = \sqrt{m \log m}$ ，则时间复杂度为 $\mathcal{O}(Q\sqrt{m \log m}\log n)$ ，用 dfs 好像是可以去掉这个 $\log n$ 的

代码：（然而还是没去写 dfs）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int n,m,S,Q,cnt1,cnt2,top,all,D[N],dl[N],op[N];
int ans[N],Id[N],sz[N],fa[N],stk[N][2]; char vis[N];
struct Edge{ int u,v,w,id; } g[N],g1[N],g2[N];
struct cxy { int op,id,W,num; } q[N],cac1[N],cac2[N];
bool cmp(Edge a,Edge b) { return a.w > b.w; }
bool cmp0(cxy a, cxy b) { return a.W > b.W; }
int find(int x) { return fa[x] == x ? fa[x] :  find(fa[x]); }
void merge(int u,int v)
{
    int x = find(u), y = find(v);
    if(x == y) return; if(sz[x] < sz[y]) swap(x,y);
    fa[y] = x; sz[x] += sz[y]; stk[++top][0] = x; stk[top][1] = y;
}
void cancel(){ int u = stk[top][0], v = stk[top--][1]; sz[u] -= sz[v]; fa[v] = v; }
void work(int len)
{
    cnt1 = cnt2 = all = top = 0;
    for(int i = 1; i <= m; i++) {
        vis[i] = D[i] = 0; Id[g[i].id] = i;
    }
    for(int i = 1; i <= len; i++)
    {
        if(q[i].op == 1)
        {
            cac1[++cnt1] = q[i]; if(vis[Id[q[i].num]]) continue;
            D[Id[q[i].num]] = g[Id[q[i].num]].w;
            vis[Id[q[i].num]] = 1; dl[++all] = Id[q[i].num];
        }else cac2[++cnt2] = q[i];
    }
    for(int i = 1; i <= n; i++) { fa[i] = i, sz[i] = 1; }
    sort(cac2 + 1, cac2 + 1 + cnt2, cmp0); int pos = 1;
    for(int i = 1; i <= cnt2; i++)
    {
        while(pos <= m && g[pos].w >= cac2[i].W) {
            if(!vis[pos]) merge(g[pos].u, g[pos].v);
            ++pos;
        }
        int las = top;
        for(int j = 1; j <= cnt1; j++) {
            if(cac1[j].id < cac2[i].id) {
                D[Id[cac1[j].num]] = cac1[j].W;
            }
        }
        for(int j = 1; j <= all; j++) {
            if(D[dl[j]] >= cac2[i].W) {
                merge(g[dl[j]].u, g[dl[j]].v);
            }
            D[dl[j]] = g[dl[j]].w;
        }
        ans[cac2[i].id] = sz[find(cac2[i].num)];
        for(; las != top; ) cancel();
    }
    int tot1 = 0, tot2 = 0;
    for(int i = 1; i <= len; i++) {
        if(q[i].op == 1) g[Id[q[i].num]].w = q[i].W;
    }
    for(int i = 1; i <= m; i++)
    {
        if(vis[i]) g1[++tot1] = g[i];
        else g[++tot2] = g[i];
    }
    sort(g1 + 1, g1 + 1 + tot1, cmp);
    merge(g + 1, g + 1 + tot2, g1 + 1, g1 + 1 + tot1, g2 + 1, cmp);
    for(int i = 1; i <= m; i++) g[i] = g2[i];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m; S = sqrt(m * log2(m));
    for(int i = 1,u,v,w; i <= m; i++) {
        cin >> u >> v >> w; g[i] = {u,v,w,i};
    }
    cin >> Q; sort(g + 1, g + 1 + m, cmp); int cnt = 0;
    for(int i = 1,x; i <= Q; i++)
    {
        q[++cnt].id = i; cin >> x; q[cnt].op = x; op[i] = x;
        cin >> q[cnt].num >> q[cnt].W; if(cnt == S) { work(S), cnt = 0; }
    }
    if(cnt) work(cnt); 
    for(int i = 1; i <= Q; i++) {
        if(op[i] == 2) cout << ans[i] << '\n';
    }
    return 0;
}