题目
题目链接：https://www.luogu.com.cn/problem/P3247
给定一张 (N) 个顶点 (M) 条边的无向图（顶点编号为 (1,2,...,n)），每条边上带有权值。所有权值都可以分解成 (2^a imes 3^b) 的形式。
现在有 (q) 个询问，每次询问给定四个参数 (u,v,a,b)，请你求出是否存在一条顶点 (u) 到 (v) 之间的路径，使得路径依次经过的边上的权值的最小公倍数为 (2^a imes 3^b)。
注意：路径可以不是简单路径。
思路
问题等价于 (u) 与 (v) 所在连通块内是否存在一张子连通图满足连接 (u) 和 (v) 且 (max(a)=a,max(b)=b)。
将边和询问均按 (a) 从小到大排序，然后给边分块。定义第 (j) 个询问“属于”第 (i) 个块当且仅当第 (j) 的询问的 (j) 大于等于第 (i-1) 个块最后一条边的 (a) 且小于第 (i) 个块最后一条边的 (a)。
对于第 (i) 个块，我们可以找出“属于”它的询问 ([l,r])，然后将 ([l,r]) 按照 (b) 排序，将前 (i-1) 个块所有边也将 (b) 排序。
此时显然对于 ([l,r]) 中任意一个询问，它的 (a) 均不小于前 (i-1) 个块的 (a)，那么此时只有 (b) 的限制了。因为按照 (b) 排序了，所以可以双指针扫描，找到对于第 (kin [l,r]) 个询问最后一个 (b) 不超过它的边，将这些边用不路径压缩，要按秩合并并查集维护每一个连通块的 (max(a)) 和 (max(b))。
对于询问 (k) “属于”的块 (i)，我们直接枚举其中的所有边，如果满足这条边的两个权值分别不超过询问的两个权值，那么就加进并查集。注意一个询问结束后需要复原它所属块的贡献。
时间复杂度 (O(msqrt{n}log n))。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=100010,M=320;
int n,m,Q,T,L[M],R[M],father[N],dep[N],maxa[N],maxb[N],cpy[N][4];
bool ans[N];
queue<int> clr;
struct edge
{
int u,v,a,b,id;
}e[N],ask[N];
bool cmp1(edge x,edge y)
{
return x.a<y.a;
}
bool cmp2(edge x,edge y)
{
return x.b<y.b;
}
int find(int x)
{
return x==father[x]?x:find(father[x]);
}
void prework()
{
for (int i=1;i<=n;i++)
{
father[i]=i; dep[i]=1;
maxa[i]=maxb[i]=-1;
}
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].a,&e[i].b);
e[++m]=(edge){0,0,(int)2e9,(int)2e9,0};
scanf("%d",&Q);
for (int i=1;i<=Q;i++)
{
scanf("%d%d%d%d",&ask[i].u,&ask[i].v,&ask[i].a,&ask[i].b);
ask[i].id=i;
}
T=sqrt(m+log2(n))+1;
for (int i=1;i<=T;i++)
L[i]=R[i-1]+1,R[i]=min(m,i*T);
sort(e+1,e+1+m,cmp1);
sort(ask+1,ask+1+Q,cmp1);
memset(cpy,-1,sizeof(cpy));
for (int i=1,r=0,l=1;i<=T;i++)
{
prework();
while (r<Q && ask[r+1].a<e[R[i]].a) r++;
sort(e+1,e+1+R[i-1],cmp2);
sort(ask+l,ask+1+r,cmp2);
for (int k=1;l<=r;l++)
{
for (;k<=R[i-1] && e[k].b<=ask[l].b;k++)
{
int x=find(e[k].u),y=find(e[k].v);
if (x==y)
{
maxa[x]=max(maxa[x],e[k].a);
maxb[x]=max(maxb[x],e[k].b);
continue;
}
if (dep[x]<dep[y])
{
father[x]=y; dep[y]=max(dep[y],dep[x]+1);
maxa[y]=max(e[k].a,max(maxa[x],maxa[y]));
maxb[y]=max(e[k].b,max(maxb[x],maxb[y]));
}
else
{
father[y]=x; dep[x]=max(dep[x],dep[y]+1);
maxa[x]=max(e[k].a,max(maxa[x],maxa[y]));
maxb[x]=max(e[k].b,max(maxb[x],maxb[y]));
}
}
for (int j=L[i];j<=R[i];j++)
if (e[j].a<=ask[l].a && e[j].b<=ask[l].b)
{
int x=find(e[j].u),y=find(e[j].v);
if (cpy[x][0]==-1)
{
cpy[x][0]=father[x]; cpy[x][1]=dep[x];
cpy[x][2]=maxa[x]; cpy[x][3]=maxb[x];
clr.push(x);
}
if (cpy[y][0]==-1)
{
cpy[y][0]=father[y]; cpy[y][1]=dep[y];
cpy[y][2]=maxa[y]; cpy[y][3]=maxb[y];
clr.push(y);
}
if (x==y)
{
maxa[x]=max(maxa[x],e[j].a);
maxb[x]=max(maxb[x],e[j].b);
continue;
}
if (dep[x]<dep[y])
{
father[x]=y; dep[y]=max(dep[y],dep[x]+1);
maxa[y]=max(e[j].a,max(maxa[x],maxa[y]));
maxb[y]=max(e[j].b,max(maxb[x],maxb[y]));
}
else
{
father[y]=x; dep[x]=max(dep[x],dep[y]+1);
maxa[x]=max(e[j].a,max(maxa[x],maxa[y]));
maxb[x]=max(e[j].b,max(maxb[x],maxb[y]));
}
}
int x=find(ask[l].u),y=find(ask[l].v);
if (x==y && maxa[x]==ask[l].a && maxb[x]==ask[l].b)
ans[ask[l].id]=1;
while (clr.size())
{
int x=clr.front(); clr.pop();
father[x]=cpy[x][0]; dep[x]=cpy[x][1];
maxa[x]=cpy[x][2]; maxb[x]=cpy[x][3];
cpy[x][0]=cpy[x][1]=cpy[x][2]=cpy[x][3]=-1;
}
}
}
for (int i=1;i<=Q;i++)
if (ans[i]) printf("Yes
");
else printf("No
");
return 0;
}