RE求助
查看原帖
RE求助
36933
zhy12138楼主2021/6/10 15:56
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<vector>
#define ll long long
using namespace std;
const int MAXN=5e4+10;
const int MAXM=1e5+10;
int read()
{
	int kkk=0,x=1;
	char c=getchar();
	while((c<'0' || c>'9') && c!='-') c=getchar();
	if(c=='-') c=getchar(),x=-1;
	while(c>='0' && c<='9') kkk=kkk*10+(c-'0'),c=getchar();
	return kkk*x;
}
int n,m,q,base,line[MAXM][3],ins[MAXM][3];
int father[MAXM],size[MAXM];
int id[MAXM],tot,Q[MAXM],cnt,mem[MAXM],pd[MAXM],ans[MAXM],C[MAXM];
int cmp(int x,int y) {return line[x][2]>line[y][2];}
int CMP(int x,int y) {return ins[x][2]>ins[y][2];}
int find(int k)
{
	if(father[k]!=k) return find(father[k]);
	return k;
}
int z[MAXM][2],top;
void merge(int k)
{
	int u=find(line[k][0]),v=find(line[k][1]);
	if(u==v) return;
	if(size[u]<size[v]) swap(u,v);
	z[++top][0]=u;
	z[top][1]=v;
	father[v]=u;
	size[u]+=size[v];
}
void del(int stp)
{
	while(top!=stp)
	{
		int u=z[top][0],v=z[top][1];
		size[u]-=size[v];
		father[v]=v;
		--top;
	}
}
int main()
{
	//freopen("a.in","r",stdin);
	n=read(),m=read();
	for(int i=1;i<=m;++i) line[i][0]=read(),line[i][1]=read(),line[i][2]=read();
	q=read();
	base=sqrt(100000*log2(100000));
	for(int i=1;i<=q;++i) ins[i][0]=read(),ins[i][1]=read(),ins[i][2]=read();
	for(int p=1;p<=(q-1)/base+1;++p)
	{
		int l=(p-1)*base+1,r=min(p*base,q);
		top=0;
		for(int i=1;i<=n;++i) father[i]=i,size[i]=1;
		cnt=C[0]=0;
		for(int i=l;i<=r;++i)
			if(ins[i][0]==1 && pd[ins[i][1]]!=p) pd[ins[i][1]]=p,C[++C[0]]=ins[i][1];
			else Q[++cnt]=i;
		sort(Q+1,Q+cnt+1,CMP);
		tot=0;
		for(int i=1;i<=m;++i) if(pd[i]!=p) id[++tot]=i;
		sort(id+1,id+tot+1,cmp);
		for(int i=1,bj=0;i<=cnt;++i)
		{
			while(bj+1<=tot && line[id[bj+1]][2]>=ins[Q[i]][2])
			{
				++bj;
				merge(id[bj]);
			}
			int tmp=top;
			for(int j=1;j<=C[0];++j) mem[C[j]]=line[C[j]][2];
			for(int j=l;j<Q[i];++j) if(ins[j][0]==1) mem[ins[j][1]]=ins[j][2];
			for(int j=1;j<=C[0];++j) if(mem[C[j]]>=ins[Q[i]][2]) merge(C[j]);
			ans[Q[i]]=size[find(ins[Q[i]][1])];
			del(tmp);
		}
		for(int i=l;i<=r;++i) if(ins[i][0]==1) line[ins[i][1]][2]=ins[i][2];
	}
	for(int i=1;i<=q;++i) if(ins[i][0]==2) printf("%d\n",ans[i]);
	return 0;
}
//ore no turn,draw!
2021/6/10 15:56
加载中...