题目描述
给定一张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，那么称路径为简单路径。
题解
大意就是说，给出一张无向图，每条边有两种边权ab，每次询问两个点和AB，问是否能找出一条路径，使得路径上所有的a都<=A,所有的b都<=B,而且路径上最大的a=A,最大的b=B。
首先考虑只有一种边权怎么做，其实就是类似克鲁斯卡尔的过程，从小到大加边，每个联通块内再维护一个最大边权，边做边处理询问就好了。
现在多了一维，怎么办。
诶，我们想到了处理多维问题的利器——KD-tree。
做法就是对于询问建KD-tree，然后把每条边在KD-tree上走一遍，挂在符合要求的节点上，然后dfs一遍这颗KD-tree，用一个带撤销的并查集维护就好了。
这是一种解法，然鹅标算是分块。
我们把边按照a排序，询问按照b排序，然后再把所有的边分块。
对于每一块，我们都把所有询问的a在这个块内的询问拿进来，这个暴力扫一遍就好了。
然后把这个块之前的所有边按照b排序。
然后处理每个询问，因为每个询问的b都是单调不降的，在当前块前面的边的b因为排过序，也是单挑不降的，而且那些边的a<=A，所以用双指针维护加边操作。
对于当前块的边，每次暴力扫暴力加，查询完之后暴力撤销回去。
细节&&卡常
于是我T飞了。
发现我的一个询问会出现在多个块里，这样就会很慢，我们希望一个询问如果能出现在多个块里的话，会出现早最后一个块中。
所以要这么写
if(q[j].a>=b[l].a&&(r==m||q[j].a<b[r+1].a))
代码
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #define N 50002 #define M 100009 using namespace std; int n,m,f[N],n1,be[M],bi,Q,deep[N],mxa[N],mxb[N],st[M]; bool ans[M]; inline int rd(){ int x=0;char c=getchar();bool f=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f?-x:x; } struct rubbish{int x,y,dep,mxa,mxb;bool tag;}ru[M]; struct node{int u,v,a,b,id;}q[M],b[M]; inline bool cmpa(node a,node b){ if(a.a!=b.a)return a.a<b.a;else return a.b<b.b; } inline bool cmpb(node a,node b){ if(a.b!=b.b)return a.b<b.b;else return a.a<b.a; } inline int find(int x){return f[x]==x?x:find(f[x]);} inline void merge(int x,int y,int a,int b){; int xx=find(x),yy=find(y); if(deep[xx]>deep[yy])swap(xx,yy); ++bi; ru[bi].x=xx;ru[bi].y=yy;ru[bi].dep=deep[yy]; ru[bi].mxa=mxa[yy];ru[bi].mxb=mxb[yy];ru[bi].tag=0; if(xx!=yy){ f[xx]=yy; deep[yy]=max(deep[yy],deep[xx]+1); ru[bi].tag=1; mxa[yy]=max(mxa[xx],mxa[yy]);mxb[yy]=max(mxb[xx],mxb[yy]); } mxa[yy]=max(mxa[yy],a);mxb[yy]=max(mxb[yy],b); } inline void pop(int x){ if(x==-1){bi=0;return;} while(x--){ int x=ru[bi].x,y=ru[bi].y,dep=ru[bi].dep; deep[y]=dep;if(ru[bi].tag)f[x]=x; mxa[y]=ru[bi].mxa;mxb[y]=ru[bi].mxb; bi--; } } int main(){ n=rd();m=rd(); n1=sqrt((double)m*log2(n)); for(int i=1;i<=m;++i){ b[i].u=rd();b[i].v=rd();b[i].a=rd();b[i].b=rd(); } Q=rd(); for(int i=1;i<=Q;++i)q[i].u=rd(),q[i].v=rd(),q[i].a=rd(),q[i].b=rd(),q[i].id=i; sort(b+1,b+m+1,cmpa);sort(q+1,q+Q+1,cmpb); int bb=(m-1)/n1+1; for(int i=1;i<=bb;++i){ //扫描所有边块 int l=(i-1)*n1+1,r=min(m,i*n1);int top=0; for(int j=1;j<=Q;++j)if(q[j].a>=b[l].a&&(r==m||q[j].a<b[r+1].a))st[++top]=j; sort(b+1,b+l,cmpb); for(int j=1;j<=n;++j){f[j]=j;deep[j]=1;mxa[j]=mxb[j]=-1;} for(int j=1,k=1;j<=top;++j){ int num=0; for(;k<l&&b[k].b<=q[st[j]].b;++k)merge(b[k].u,b[k].v,b[k].a,b[k].b); for(int o=l;o<=r;++o)if(b[o].a<=q[st[j]].a&&b[o].b<=q[st[j]].b) merge(b[o].u,b[o].v,b[o].a,b[o].b),num++; int xx=find(q[st[j]].u),yy=find(q[st[j]].v); if(xx==yy&&mxa[xx]==q[st[j]].a&&mxb[xx]==q[st[j]].b)ans[q[st[j]].id]=1; pop(num); } pop(-1); } for(int i=1;i<=Q;++i)if(ans[i])puts("Yes"); else puts("No"); return 0; }