首页 > 代码库 > bzoj4537: [Hnoi2016]最小公倍数
bzoj4537: [Hnoi2016]最小公倍数
Description
给定一张N个顶点M条边的无向图(顶点编号为1,2,…,n)，每条边上带有权值。所有权值都可以分解成2^a*3^b
的形式。现在有q个询问，每次询问给定四个参数u、v、a和b，请你求出是否存在一条顶点u到v之间的路径，使得
路径依次经过的边上的权值的最小公倍数为2^a*3^b。注意：路径可以不是简单路径。下面是一些可能有用的定义
：最小公倍数：K个数a1,a2,…,ak的最小公倍数是能被每个ai整除的最小正整数。路径：路径P:P1,P2,…,Pk是顶
点序列，满足对于任意1<=i<k，节点Pi和Pi+1之间都有边相连。简单路径：如果路径P:P1,P2,…,Pk中，对于任意1
<=s≠t<=k都有Ps≠Pt，那么称路径为简单路径。
Input
输入文件的第一行包含两个整数N和M，分别代表图的顶点数和边数。接下来M行，每行包含四个整数u、v、a、
b代表一条顶点u和v之间、权值为2^a*3^b的边。接下来一行包含一个整数q，代表询问数。接下来q行，每行包含四
个整数u、v、a和b，代表一次询问。询问内容请参见问题描述。1<=n,q<=50000、1<=m<=100000、0<=a,b<=10^9
Output
对于每次询问，如果存在满足条件的路径，则输出一行Yes，否则输出一行 No（注意：第一个字母大写，其余
字母小写） 。
存在合法路径等价于只保留a,b均不超过询问值的边，两点联通且a,b的最值分别能取到
对分块实现的莫队算法稍作修改就可以处理这个问题
将边按a分块，保证a相同的边分在同一块，且块大小尽可能在O(n/sqrt(m))
询问也分到对应的块中，对每个块，按b升序处理，左边的块内的边可以直接在并查集上修改，当前块内暴力修改和撤销
但若块大小因为a相同分到同一块的限制而较大则不能保证复杂度，对这种特殊情况，由于特殊性可以把当前块和左边的块内的边一起处理而不用撤销
总复杂度O(nsqrt(m)logn+mlongm)
#include<cstdio>#include<cmath>#include<algorithm>#include<cstring>#define G *++ptrconst int N=50007;char buf[10000007],*ptr=buf-1;int _(){ int x=0,c=G; while(c<48)c=G; while(c>47)x=x*10+c-48,c=G; return x;}int n,m,q;bool as[N];int f[N],xm[N],ym[N],B,bs[N],bp=0,*o1[N],o2[N],op=0;void undo(){ while(op)--op,*o1[op]=o2[op];}inline void set(int*x,int y){ o1[op]=x; o2[op++]=*x; *x=y;}void init(){ memset(f,-1,sizeof(int)*(n+2)); memset(xm,-1,sizeof(int)*(n+2)); memset(ym,-1,sizeof(int)*(n+2));}inline int gf(int x){ while(f[x]>0)x=f[x]; return x;}struct Q{ int u,v,x,y,id; void init(int i){ u=_();v=_();x=_();y=_(); id=i; } void cal(){ int a=gf(u),b=gf(v); if(a==b&&xm[a]==x&&ym[b]==y)as[id]=1; }}qs[N];bool qcmpx(const Q&a,const Q&b){return a.x<b.x;}bool qcmpy(const Q&a,const Q&b){return a.y<b.y;}int max(int a,int b){return a>b?a:b;}struct edge{ int u,v,x,y; void init(){ u=_();v=_();x=_();y=_(); } void cal(){ int a=gf(u),b=gf(v); if(a!=b){ if(f[a]<f[b])std::swap(a,b); if(f[a]==f[b])--f[b]; f[a]=b; } int xx=max(xm[a],x),yy=max(ym[a],y); if(xx>xm[b])xm[b]=xx; if(yy>ym[b])ym[b]=yy; } void cal_(){ int a=gf(u),b=gf(v); if(a!=b){ if(f[a]<f[b])std::swap(a,b); if(f[a]==f[b])set(f+b,f[b]-1); set(f+a,b); } int xx=max(xm[a],x),yy=max(ym[a],y); if(xx>xm[b])set(xm+b,xx); if(yy>ym[b])set(ym+b,yy); }}e[N*2];bool ecmpx(const edge&a,const edge&b){return a.x<b.x;}bool ecmpy(const edge&a,const edge&b){return a.y<b.y;}void msort(edge*l,edge*m,edge*r){ static edge ee[N*2]; std::sort(m,r,ecmpy); if(l==m||m==r)return; edge*p1=l,*p2=m,*p3=ee; while(p1!=m&&p2!=r)*p3++=p1->y<p2->y?*p1++:*p2++; while(p1!=m)*p3++=*p1++; while(p2!=r)*p3++=*p2++; memcpy(l,ee,(p3-ee)*sizeof(edge));}int main(){ fread(buf,1,sizeof(buf),stdin)[buf]=0; n=_();m=_(); B=n/sqrt(m+1)*2+1; for(int i=0;i<m;++i)e[i].init(); q=_(); for(int i=0;i<q;++i)qs[i].init(i); std::sort(qs,qs+q,qcmpx); std::sort(e,e+m,ecmpx); for(int i=0,j=0;i<m;i=j){ for(;j<m&&e[i].x==e[j].x;++j); if(j-bs[bp]>B)bs[++bp]=i; } e[bs[++bp]=m].x=0x3f3f3f3f; for(int b=0,l=0,r=0,S=0;b<bp;++b){ int L=bs[b],R=bs[b+1]; for(l=r;r<q&&qs[r].x<e[R].x;++r); std::sort(qs+l,qs+r,qcmpy); if(e[L].x==e[R-1].x){ msort(e,e+S,e+R);S=R; init(); for(int ep=0,p=l;p<r;++p){ Q&w=qs[p]; for(;ep<R&&e[ep].y<=w.y;++ep)e[ep].cal(); w.cal(); } }else{ msort(e,e+S,e+L);S=L; init(); for(int ep=0,p=l;p<r;++p){ Q&w=qs[p]; for(;ep<L&&e[ep].y<=w.y;++ep)e[ep].cal(); for(int ep=L;ep<R;++ep)if(e[ep].x<=w.x&&e[ep].y<=w.y)e[ep].cal_(); w.cal(); undo(); } } } for(int i=0;i<q;++i)puts(as[i]?"Yes":"No"); return 0;}
bzoj4537: [Hnoi2016]最小公倍数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。