自动搬运

查看原文

来自洛谷，原作者为

	mrsrz 故障机器人

搬运于2025-08-24 22:10:48，当前版本为作者最后更新于2019-07-10 10:18:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

操作分块+可撤销并查集。

我们将操作进行分块，对每块的询问进行处理。设块大小为$S$。

对当前块之前的修改可以直接修改掉。

对每个块，都有一部分边会被修改，这些边的个数不超过$S$。而剩下的边不会被修改。询问的个数也不会超过$S$。

将询问按照重量从大到小排序，边也按重量限制从大到小排序。枚举询问，把满足重量限制的不会被修改的边加入即可。用并查集维护。

考虑会被修改的边产生的影响。由于这些边的个数并不多，我们对每个询问，把符合条件的边暴力插入即可。处理完这个询问，再把这些边暴力删掉即可。

需要用到可撤销并查集。

每个块处理的复杂度为$O(m\log m+S^2\log n)$。

根据实际情况取块大小即可。理论复杂度$O(q\sqrt q\log m)$。

可以把$O(m\log m)$的排序用归并优化掉$\log$。则理论复杂度可以做到$O(q\sqrt{q\log m})$。

看起来log放根号外面也挺快的啊

Code：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e5+7,siz=1024;
int n,m;
struct edge{
	int u,v,w,id;
	inline int operator<(const edge&rhs)const{return w>rhs.w;}
}e[N];
inline int cmp(const edge&a,const edge&b){return a.id<b.id;}
int ans[N];
struct f_t{
	int bc,id,tim;
	inline int operator<(const f_t&rhs)const{return bc>rhs.bc;}
};
vector<f_t>M,Q;
int q;
int fa[N],sz[N],sta[N],top,vis[N],ys[N];
inline int find(int x){return x==fa[x]?x:find(fa[x]);}
inline void merge(int u,int v){
	u=find(u),v=find(v);
	if(u==v)return;
	if(sz[u]<sz[v])swap(u,v);
	sta[++top]=v;
	sz[u]+=sz[v],fa[v]=u;
}
void back(int lst){
	while(top>lst){
		int v=sta[top--];
		sz[fa[v]]-=sz[v];
		fa[v]=v;
	}
}
void solve(){
	sort(e+1,e+m+1);
	sort(Q.begin(),Q.end());
	for(int i=1;i<=m;++i)ys[e[i].id]=i;
	static vector<f_t>MM;MM.clear();
	for(f_t i:M)vis[i.id]=-1,MM.push_back((f_t){e[ys[i.id]].w,i.id,0});
	for(f_t i:M)MM.push_back(i);
	for(int i=1;i<=n;++i)fa[i]=i,sz[i]=1;
	top=0;
	for(int i=0,it=1;i<Q.size();++i){
		while(it<=m&&e[it].w>=Q[i].bc){
			if(!vis[e[it].id])merge(e[it].u,e[it].v);
			++it;
		}
		int last=top;
		for(f_t a:MM)
		if(a.tim<=Q[i].tim)vis[a.id]=a.bc;
		for(f_t a:M)
		if(vis[a.id]>=Q[i].bc)merge(e[ys[a.id]].u,e[ys[a.id]].v);
		ans[Q[i].tim]=sz[find(Q[i].id)];
		back(last);
	}
	for(f_t i:M)e[ys[i.id]].w=i.bc,vis[i.id]=0;
	M.clear(),Q.clear();
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;++i)cin>>e[i].u>>e[i].v>>e[e[i].id=i].w;
	cin>>q;
	for(int t=1;t<=q;++t){
		int op;f_t x;
		cin>>op>>x.id>>x.bc;
		x.tim=t;
		if(op==1)M.push_back(x);else Q.push_back(x);
		if(t%siz==0)solve();
	}
	if(q%siz)solve();
	for(int i=1;i<=q;++i)if(ans[i])cout<<ans[i]<<'\n';
	return 0;
}