萌新求助,8pts,其他全WA
查看原帖
萌新求助,8pts,其他全WA
310802
_Diu_楼主2021/12/20 19:50
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,q,fa[N],sz[N],is[N];
int tot,ans[N],vis[N],num[N],bsp[N];
struct edge{
	int u,v,w,id;
}e[N];
bool cmp(edge a,edge b){return a.w>b.w;}
struct que{
	int a,b,t;
}chg[N],qry[N];
bool cmpp(que a,que b){return a.b>b.b;}
int t1,t2;
int find(int x){
	return fa[x]==x?x:find(fa[x]);
}
void merge(int u,int v){
	u=find(u),v=find(v);
	if(u==v)return;
	if(sz[u]<sz[v])swap(u,v);
	bsp[++tot]=v;
	sz[u]+=sz[v],fa[v]=u;
}
void back(int lst){
	while(tot>lst){
		int v=bsp[tot--];
		sz[fa[v]]-=sz[v],fa[v]=v;
	}
}
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w),e[i].id=i;
	scanf("%d",&q);
	int B=sqrt(m*log2(n));
	for(int k=1,end;k<=q;k=end+1){
		end=min(k+B-1,q);
		t1=t2=0;
		for(int i=k,op;i<=end;i++){
			scanf("%d",&op);
			if(op^2)++t1,scanf("%d%d",&chg[t1].a,&chg[t1].b),chg[t1].t=i;
			else ++t2,scanf("%d%d",&qry[t2].a,&qry[t2].b),qry[t2].t=i;
		}
		sort(e+1,e+m+1,cmp);
		sort(qry+1,qry+t2+1,cmpp);
		for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1,vis[i]=0;
		for(int i=1;i<=m;i++)num[e[i].id]=i;
		for(int j=1;j<=t1;j++)vis[chg[j].a]=-1;
		for(int i=1,p=1;i<=t2;i++){
			while(p<=m&&e[p].w>=qry[i].b){
				if(!vis[e[p].id])merge(e[p].u,e[p].v);
				++p;
			}
			int lst=tot;
			for(int j=1;j<=t1;j++)vis[chg[j].a]=e[num[chg[j].a]].w;
			for(int j=1;j<=t1&&chg[j].t<qry[i].t;j++)vis[chg[j].a]=chg[j].b;
			for(int j=1;j<=t1;j++)if(vis[chg[j].a]>=qry[i].b)merge(e[num[chg[j].a]].u,e[num[chg[j].a]].v);
			ans[qry[i].t]=sz[find(qry[i].a)];
			back(lst);
		}
		for(int i=1;i<=t1;i++)e[num[chg[i].a]].w=chg[i].b;
	}
	for(int i=1;i<=q;i++)if(ans[i])printf("%d\n",ans[i]);
}
2021/12/20 19:50
加载中...