loj#2048. 「HNOI2016」最小公倍数 ( JSOIP2022练习赛1 t1 )

给定一张 \(n\) 个顶点 \(m\) 条边的无向图（顶点编号为 \(1,2,3,\cdots,n\)），每条边上带有权值。所有权值都可以分解成 \(2^a\cdot 3^b\)的形式。

现在有 \(q\) 个询问，每次询问给定四个参数 \(u\) 、\(v\) 、\(a\) 和 \(b\) ，请你求出是否存在一条顶点 \(u\) 到 \(v\) 之间的路径，使得路径依次经过的边上的权值的最小公倍数为 \(2^a\cdot 3^b\) 。

\(1\leq n,q\leq 5\cdots 10^4,1\leq m\leq 10^5,0\leq a,b\leq 10^9\) .

首先观察到如何判断最小公倍数是 \(2^a\cdot 3^b\) .

考虑加入 \(2^{a_0}\cdot 3^{b_0}\) 的边，其中 \(a_0\leq a,b_0\leq b\) , 此时会构成一个图，考虑图的联通情况用 \(\rm{dsu}\) 维护 . 如果 \(u,v\) 之间存在最小公倍数是 \(2^a\cdot 3^b\) 的路径，必须要满足下面 3 个条件 。

1. \(u,v\) 联通 .
2. \(u,v\) 所在联通块 \(2\) 的幂次最大值恰好为 \(a\) .
3. \(u,v\) 所在连通块 \(3\) 的幂次最大值恰好为 \(b\) .

确定了使用 \(\rm{dsu}\) 进行判断，但是出现了一个问题 \(a\) 和 \(b\) 有两个维度，如何用可行的复杂度控制当前图上的 \(a,b\) 大小 .

首先要控制 \(a\) 的大小，对边按照 \(a\) 排序，接着对边分块，每块的大小是 \(S\) . 设当前块的 \(a\) 的最大值为 \(mx\) ，最小值为 \(mn\) .

现在，就是要处理出 \(mn\leq a_0 的询问 . 因为我们**控制住了当前块的边数大小只有 \(S\) **，所以，对于每个询问，相当于我们可以操作 \(O(S)\) 条边. 此时，就需要保证 \(b\) 的大小顺序，将 \(b\) 从小到大递增 . 对于符合要求的询问按照 \(b\) 从小到大排序 .

在询问的同时按照 \(b\) 的大小依次扩展 \(a 的边 . 对于 \(a\) 来说，\(a\) 的变化只会在 \(S\) 条边中 . 于此同时，我们还需要可撤销并查集来支持 \(S\) 条边的操作 .

对于块外 \(a 的边的复杂度是 \(O(\frac{m}{S}m\alpha(n))\) 的. 块内的边复杂度则是 \(O(qS\alpha(n))\) 的 .

时间复杂度 : \(O(\frac{m}{S}m\alpha(n)+qS\alpha(n))\)

空间复杂度 : \(O(n+m)\)

当 \(S\) 的大小取到 \(800\) 的时候最快 .

code

#include
using namespace std;
char in[100005];
int iiter=0,llen=0;
inline char get(){
	if(iiter==llen)llen=fread(in,1,100000,stdin),iiter=0;
	if(llen==0)return EOF;
	return in[iiter++];
}
inline int rd(){
	char ch=get();while(ch<'0'||ch>'9')ch=get();
	int res=0;while(ch>='0'&&ch<='9')res=(res<<3)+(res<<1)+ch-'0',ch=get();
	return res;
}
inline void pr(int res){
	if(res==0){putchar('0');return;}
	static int out[10];int len=0;
	while(res)out[len++]=res%10,res/=10;
	for(int i=len-1;i>=0;i--)putchar(out[i]+'0');
}
const int N=5e4+10,M=1e5+10;
const int B=810;
int n,m,q;
class edge{public:int u,v,a,b;}e[M];
class query{public:int u,v,a,b,id;}qr[N];
bool ans[N],ok[N];
inline bool cmpa(const edge&A,const edge&B){return A.asz[u])swap(u,v);
	if(!tp){
		x2[u]=max(x2[u],a);x3[u]=max(x3[u],b);
		if(u==v)return;
		fa[v]=u;sz[u]+=sz[v];
		x2[u]=max(x2[u],x2[v]);x3[u]=max(x3[u],x3[v]);
	}else{
		s[++top]=(edge){u,u!=v?v:-1,x2[u],x3[u]}; 
		x2[u]=max(x2[u],a);x3[u]=max(x3[u],b);
		if(u==v)return;
		fa[v]=u;sz[u]+=sz[v];
		x2[u]=max(x2[u],x2[v]);x3[u]=max(x3[u],x3[v]);
	}
}
void undo(){
	while(top){
		int u=s[top].u,v=s[top].v,a=s[top].a,b=s[top].b;
		x2[u]=a;x3[u]=b;
		if(v!=-1)fa[v]=v,sz[u]-=sz[v];
		top--;
	}
}
inline int qry(int u,int v,int a,int b){
	u=get_fa(u);v=get_fa(v);
	if(u!=v)return false;
	return x2[u]==a&&x3[u]==b;
}
int main(){
	n=rd();m=rd();
	for(int i=0;ir)break;
		vectorve;
		for(int i=0;i