[HNOI2016]最小公倍数

题目描述

给定一张N个顶点M条边的无向图(顶点编号为1,2,…,n)，每条边上带有权值。所有权值都可以分解成2^a*3^b
的形式。现在有q个询问，每次询问给定四个参数u、v、a和b，请你求出是否存在一条顶点u到v之间的路径，使得
路径依次经过的边上的权值的最小公倍数为2^a*3^b。注意：路径可以不是简单路径。下面是一些可能有用的定义
：最小公倍数：K个数a₁,a₂,…,a_k的最小公倍数是能被每个a_i整除的最小正整数。路径：路径P:P₁,P₂,…,P_k是顶
点序列，满足对于任意1<=i<k，节点P_i和P_i+1之间都有边相连。简单路径：如果路径P:P₁,P₂,…,P_k中，对于任意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;
}