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}\)。
Solution:
好神的并查集。
说句闲话：
主播在考场上场切了这题，然后赛后讲评时由于社恐导致思维混乱，在讲台上乱讲了半天然后什么都没将明白 TAT
让我们重整思维：
首先看到这个题目我先想到的是 kruskal 重构树，对于时间序列分块然后对于每个询问先 \(O(\log n)\) 的在 kruskal 重构树上跳，然后在考虑散块上的操作对此询问的影响，但是散块上的操作并不能 \(O(1)\) 处理掉，还要挂到数据结构上，多一个 \(log\)，而且并不好实现，所以我就抛了。
但是我们发现这个思考是十分有价值的，因为 kruskal 重构树的本质就是并查集。所以我们考使用并查集来维护联通块的信息。然后我们再思考一下以上算法为什么时间并不优秀：我们 \(O(n\log n)\) 建了一颗 kruskal 重构树，但是它只被访问了不到 \(B\) 次就扔掉了。由此可见，我们并不关心全局的图如何，我们只关心在我们询问上且边权符合条件的点。
预处理部分：
我们考虑继续对时间进行分块，对于每个块，我们在块内对于询问按照其权值 \(w_i\) 降序排序,记当前询问的时间是 \(tim_i\),当前时间块的区间为 \([l,r]\)。然后我们维护一下哪些边 \(E\) 在 \([l,r]\) 上未曾被修改，然后将 \(E\) 按照边权降序排序。对于在区间 \([l,r]\) 上修改过的边，我们维护一个集合 \(U\)，同时记录每个边被修改的时间 \(t_{id}\)。
实现：
然后我们在按照 \(w_i\) 降序处理询问的同时对于 \(E\) 跑一个双指针。如果条边的权值满足要求，就将其加入图中，这样我们就保证了通过 \(E\) 加入并查集的边不会被撤销。这样我们对于每个询问，都能得到在 \(l\) 时刻满足 \(E_w\ge w_i\) 的所有点并查集。
然后我们思考怎么处理块内的更新对于询问的影响：
我们在修改边集 \(U\) 上暴力扫一遍在 \(tim_i\) 时刻生效的修改，然后将满足 \(b_{id}' \ge w_i\) 的新边尝试加入到并查集中，对于修改在 \(tim_i\) 时刻未生效的边，则考虑原边。
在块内，我们的询问在时间上是无序的，所有我们在每次将修改边插入并查集后要将所有的修改边和修改未生效的原边全部删除。详见代码。
时间复杂度分析：
我们在每个块内要重新排一遍序，时间复杂度 \(O(m\log m)\)
每个询问要暴力扫一遍块内的修改时间复杂度 \(O(B^2)\)
剩下不占大头，几乎可以忽略，总时间复杂度 \(O((m\log m+B^2)\times \frac{m}{B})\) 当且仅当 \(B=\sqrt{m\log m}\) 时取得 \(O(m\sqrt{m\log m})\)。
然后这题就做完了。
Code:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int len;
int siz[N],fa[N],sta[N],ans[N];
inline 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);sta[++sta[0]]=y;siz[x]+=siz[y];fa[y]=x;
}
void pop(int tim)
{while(sta[0]>tim){int x=sta[sta[0]--];siz[fa[x]]-=siz[x];fa[x]=x;}
}
struct data{int w,id,tim;bool operator<(const data &a)const{return w>a.w;}
};
vector<data> Q,U;//query,upd
struct Edge{int u,v,w,id;bool operator<(const Edge &e){return w>e.w;}
};
vector<Edge> e;
int n,m,q;
int rid[N],val[N];//val : 当前边是否在线，在线时权值
vector<data> UU;//当前时间块可能要用到的所有有修改的边
void solve()
{for(int i=1;i<=n;i++)siz[fa[i]=i]=1;sta[0]=0;sort(Q.begin(),Q.end());sort(e.begin(),e.end());for(int i=0;i<m;i++)rid[e[i].id]=i;for(data u : U){val[u.id]=-1;UU.push_back(data{e[rid[u.id]].w,u.id,0});}//存原边for(data u : U)UU.push_back(u);//改边全在原边后，遍历到就改for(int i=0,j=0;i<Q.size();i++){while(j<m&&e[j].w>=Q[i].w){if(val[e[j].id]==0)merge(e[j].u,e[j].v);//当前边在该时间块内未修改j++;}int last=sta[0];for(data uu : UU)if(uu.tim<=Q[i].tim)val[uu.id]=uu.w;for(data u : U)if(val[u.id]>=Q[i].w)merge(e[rid[u.id]].u,e[rid[u.id]].v);ans[Q[i].tim]=siz[find(Q[i].id)];pop(last);}for(data u : U){Edge ee=e[rid[u.id]];ee.w=u.w;val[u.id]=0;e.erase(e.begin()+rid[u.id]);e.insert(lower_bound(e.begin(),e.end(),ee),ee);}Q.clear();U.clear();UU.clear();
}
void work()
{cin>>n>>m;len=sqrt(m*log(m)/log(2));for(int i=1,u,v,w;i<=m;i++){scanf("%d%d%d",&u,&v,&w);e.push_back(Edge{u,v,w,i});}sort(e.begin(),e.end());cin>>q;for(int i=1,opt;i<=q;i++){data d={0,0,0};scanf("%d%d%d",&opt,&d.id,&d.w);d.tim=i;if(opt==1)U.push_back(d);else Q.push_back(d);if(i%len==0)solve();}if(q%len)solve();for(int i=1;i<N;i++)if(ans[i])printf("%d\n",ans[i]);
}
int main()
{//freopen("lake.in","r",stdin);//freopen("lake.out","w",stdout);work();return 0;
}