记录编号	600967	评测结果	AAAAAAAAAA
题目名称	2241.[HNOI 2016] 最小公倍数	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	6.114 s
提交时间	2025-05-22 14:41:32	内存使用	7.15 MiB

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+7;
int n,m,q,sz,ct=1,rs[N],f[N],d[N],mx[N],my[N];
struct E{int u,v,a,b,id;}e[N],qr[N],t[N],h[N];

bool cmpA(E&x,E&y){return x.a<y.a||(x.a==y.a&&x.b<y.b);}
bool cmpB(E&x,E&y){return x.b<y.b||(x.b==y.b&&x.a<y.a);}

int fd(int x){while(f[x])x=f[x];return x;}

void mg(int i,int j){
    int x=fd(e[i].u),y=fd(e[i].v);
    if(d[x]<d[y])swap(x,y);
    if(j)h[j]={x,y,mx[x],my[x],d[x]};
    mx[x]=max({mx[x],mx[y],e[i].a});
    my[x]=max({my[x],my[y],e[i].b});
    if(x!=y)f[y]=x,d[x]+=d[x]==d[y];
}

void sp(int j){
    E&k=h[j];
    mx[k.u]=k.a,my[k.u]=k.b,d[k.u]=k.id;
    if(k.u!=k.v)f[k.v]=0;
}

bool ck(E&k){
    int x=fd(k.u),y=fd(k.v);
    return x==y&&mx[x]==k.a&&my[x]==k.b;
}

void sol(int b){
    fill_n(f,n+1,0);fill_n(d,n+1,0);
    fill_n(mx,n+1,-1);fill_n(my,n+1,-1);
    int M=sz*b<m?e[sz*b+1].a:2e9,ed=(b-1)*sz,c=0,tp=0;
    while(ct<=q&&qr[ct].a<M)t[++c]=qr[ct++];
    if(!c)return;
    sort(t+1,t+c+1,cmpB);
    sort(e+1,e+ed+1,cmpB);
    for(int i=1,j=1;i<=c;i++){
        for(;j<=ed&&e[j].b<=t[i].b;j++)mg(j,0);
        for(int k=ed+1;k<=m&&e[k].a<=t[i].a;k++)
            if(e[k].b<=t[i].b)mg(k,++tp);
        rs[t[i].id]=ck(t[i]);
        while(tp)sp(tp--);
    }
}

int main(){
	freopen("multiple.in","r",stdin); freopen("multiple.out","w",stdout);
    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);
    scanf("%d",&q);
    for(int i=1;i<=q;i++)qr[i].id=i,scanf("%d%d%d%d",&qr[i].u,&qr[i].v,&qr[i].a,&qr[i].b);
    
    sz=sqrt(m+1);
    sort(e+1,e+m+1,cmpA);
    sort(qr+1,qr+q+1,cmpA);
    
    for(int i=1;sz*(i-1)<m;i++)sol(i);
    for(int i=1;i<=q;i++)puts(rs[i]?"Yes":"No");
}