zcmimi's blog
查看原题

点击跳转

题意:

给出n个点m条边的无向图,每条边u\leftrightarrow v有两个权值a,b

q个询问,给出u,v,A,Bu,v间是否存在路径\max\{a\}=A\max\{b\}=B

先考虑最暴力的做法:

把所有符合条件的边(a\le A,b\le B)添加到并查集,

然后判断最大值是不是A,Bu,v是否连通

接着对边排序、回滚莫队,使用按秩合并并查集(可撤销并查集)

m条边按a进行排序

对询问按b进行排序

m条边进行分块

对每个块处理符合a大于等于该块\max\{a\}的询问

把当前块前面的点按照b排序(使b单调递增)

开始处理询问:

当前块前面的点的b是单调递增的,而a一定符合条件 ,所以可以一直右移指针添加符合条件的边

然后枚举块中的边,添加符合当前询问的边,得到当前询问答案,回滚,删掉当前询问添加的边

下一个询问

处理完当前块后,暴力清空并查集

分块大小为\sqrt{m\log n}时复杂度最优

#include<bits/stdc++.h>
const int N=100011;
int n,m,k,blk,f[N],siz[N],ma[N],mb[N],tp=0;
bool ans[N];
int gf(int x){return x==f[x]?x:gf(f[x]);}
struct edge{
    int u,v,a,b,k;
    void in(){scanf("%d%d%d%d",&u,&v,&a,&b);}
}a[N],q[N],c[N],d[N];
void cmax(int&x,int y){if(y>x)x=y;}
void mg(edge x,bool typ=0){
    int u=gf(x.u),v=gf(x.v);
    if(siz[u]>siz[v])u^=v,v^=u,u^=v;
    if(typ)d[++tp]=(edge){u,v,ma[v],mb[v],siz[v]};
    if(u!=v)
        f[u]=v,siz[v]+=siz[u],
        cmax(ma[v],ma[u]),cmax(mb[v],mb[u]);
    cmax(ma[v],x.a),cmax(mb[v],x.b);
}
void br(edge x){
    f[x.u]=x.u;
    ma[x.v]=x.a,mb[x.v]=x.b,siz[x.v]=x.k;
}
bool cmpa(edge x,edge y){return x.a==y.a?x.b<y.b:x.a<y.a;}
bool cmpb(edge x,edge y){return x.b==y.b?x.a<y.a:x.b<y.b;}
int main(){
    scanf("%d%d",&n,&m);blk=sqrt(m*log2(n));
    for(int i=1;i<=m;++i)a[i].in();
    scanf("%d",&k);
    for(int i=1;i<=k;++i)q[i].in(),q[i].k=i;
    std::sort(a+1,a+m+1,cmpa);
    std::sort(q+1,q+k+1,cmpb);
    for(int i=blk;i<=m;i+=blk){
        for(int j=1;j<=n;++j)
            f[j]=j,siz[j]=1,ma[j]=mb[j]=-1;
        int tt=0;
        for(int j=1;j<=k;++j)
            if(a[i].a<=q[j].a&&(a[i+blk].a>q[j].a||i+blk>m))
                c[++tt]=q[j];
        if(!tt)continue;
        std::sort(a+1,a+i,cmpb);
        for(int j=1,t=1;j<=tt;++j){
            for(;t<i&&a[t].b<=c[j].b;++t)mg(a[t]);
            for(int l=i;l<i+blk&&l<=m;++l)
                if(a[l].a<=c[j].a&&a[l].b<=c[j].b)mg(a[l],1);
            int u=gf(c[j].u),v=gf(c[j].v);
            ans[c[j].k]=(u==v&&ma[u]==c[j].a&&mb[u]==c[j].b);
            while(tp)br(d[tp--]);
        }
    }
    for(int i=1;i<=k;++i)puts(ans[i]?"Yes":"No");
}
LG 3247 [HNOI2016]最小公倍数
comment评论
Search
search