题解洛谷 P3247 【[HNOI2016]最小公倍数】

题意可以转化为是否能找一条从\(u\)到\(v\)的路径，经过的边的\(a\)和\(b\)的最大值恰好都是询问所给定的值。

若只有\(a\)的限制，可以将询问离线，对边和询问都从小到大排序，然后双指针维护当前合法的边，用并查集维护连通块的最值和连通性。

现在有\(a\)和\(b\)的限制，考虑对边分块，先对所有边按\(a\)从小到大排序，对所有询问按\(b\)从小到大排序。

考虑当前枚举到的一个块及其之前块对询问的贡献。对所有询问找到\(a\)大小恰好在当前块范围内的询问，对当前块之前的整块按\(b\)从小到大排序，这样就能保证在当前块之前的所有边的\(a\)都小于等于现在找到的这些询问，然后这些边对\(b\)都有序，因为已经事先已经对询问排过序，所以可以像只有一个限制时一样，对当前块之前的整块进行双指针维护对当前询问合法的边。

对于零散块内的边，可以直接暴力枚举，如果合法就加入，当考虑到下一个询问时，对于零散块内加入的边要执行删除，所以用可撤销并查集来维护即可。

\(code:\)

#include<bits/stdc++.h>

#define maxn 200010

using namespace std;

template<typename T> inline void read(T &x)

{

    x=0;char c=getchar();bool flag=false;

    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

    if(flag)x=-x;

}

int n,m,qu,S,top;

int ans[maxn],fa[maxn],de[maxn],va[maxn],vb[maxn];

struct node

{

    int x,y,a,b,id;

}e[maxn],q[maxn],t[maxn];

bool cmp1(const node &x,const node &y)

{

    if(x.a==y.a) return x.b<y.b;

    return x.a<y.a;

}

bool cmp2(const node &x,const node &y)

{

    if(x.b==y.b) return x.a<y.a;

    return x.b<y.b;

}

struct Node

{

    int x,y,deep,a,b;

}st[maxn];

int find(int x)

{

    return fa[x]==x?x:find(fa[x]);

}

void merge(int x,int y,int a,int b)

{

    x=find(x),y=find(y);

    if(de[x]<de[y]) swap(x,y);

    st[++top]=(Node){x,y,de[x],va[x],vb[x]};

    va[x]=max(va[x],a),vb[x]=max(vb[x],b);

    if(x==y) return;

    fa[y]=x,de[x]=max(de[x],de[y]+1);

    va[x]=max(va[x],va[y]),vb[x]=max(vb[x],vb[y]);

}

bool query(int id)

{

    int x=find(t[id].x),y=find(t[id].y);

    if(x!=y) return false;

    if(va[x]!=t[id].a||vb[x]!=t[id].b) return false;

    return true;

}

void del(int id)

{

    int x=st[id].x,y=st[id].y;

    fa[y]=y,de[x]=st[id].deep,va[x]=st[id].a,vb[x]=st[id].b;

}

int main()

{

    read(n),read(m),S=sqrt(m*log2(n));

    for(int i=1;i<=m;++i)

        read(e[i].x),read(e[i].y),read(e[i].a),read(e[i].b);

    read(qu);

    for(int i=1;i<=qu;++i)

        read(q[i].x),read(q[i].y),read(q[i].a),read(q[i].b),q[i].id=i;

    sort(e+1,e+m+1,cmp1),sort(q+1,q+qu+1,cmp2);

    for(int i=1;i<=m;i+=S)

    {

        int tot=0,pos=1;

        for(int j=1;j<=n;++j) fa[j]=j,va[j]=vb[j]=-1,de[j]=0;

        for(int j=1;j<=qu;++j)

            if(q[j].a>=e[i].a&&(q[j].a<e[i+S].a||i+S>m))

                t[++tot]=q[j];

        if(!tot) continue;

        if(i!=1) sort(e+1,e+i,cmp2);

        for(int j=1;j<=tot;++j)

        {

            while(pos<i&&e[pos].b<=t[j].b)

                merge(e[pos].x,e[pos].y,e[pos].a,e[pos].b),pos++;

            top=0;

            for(int k=i;k<i+S&&k<=m;++k)

                if(e[k].a<=t[j].a&&e[k].b<=t[j].b)

                    merge(e[k].x,e[k].y,e[k].a,e[k].b);

            ans[t[j].id]=query(j);

            while(top) del(top--);

        }

    }

    for(int i=1;i<=qu;++i)

    {

        if(ans[i]) puts("Yes");

        else puts("No");

    }

    return 0;

}

巴特西

题解洛谷 P3247 【[HNOI2016]最小公倍数】

最新文章

热门文章

巴特西

题解 洛谷 P3247 【[HNOI2016]最小公倍数】

最新文章

热门文章

题解洛谷 P3247 【[HNOI2016]最小公倍数】