BZOJ4537 HNOI2016最小公倍数（莫队+并查集）

　　考虑边只有一种权值的简化情况。那么当且仅当两点可以通过边权<=x的边连通，且连通块内最大边权为x时，两点间存在路径max为x的路径。可以发现两种权值是类似的，当且仅当两点可以通过边权1<=x且边权2<=y的边连通，且连通块内最大边权1为x、最大边权2为y时，两点间存在路径max为(x,y)的路径。

　　一种权值的情况很好处理，从小到大加边并查集维护即可。观察数据范围容易想到根号算法。考虑类似回滚莫队的做法。按边权1将边分块，块内按边权2排序。处理某块时将所有权值1恰好小于该块max的询问找出来按边权2排序，依次处理，每次加入之前块中边权2不大于它的边，然后在块内暴力找满足条件的边加入，使用带撤销并查集即可维护。

　　注意存在u=v，a=b=0的询问，所以集合内权值最大值的初值不能设成0。

　　调了半天以为有什么细节问题，结果发现并查集整个写错了，居然luogu还有80分数据水爆了啊。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 50010

#define M 100010

#define inf 1000000000

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int n,m,q,t,L[N],R[N],fa[N],mx[N],mxa[N],mxb[N],ans[N],cur[N],size[N],cnt;

int top;

struct data

{

    int x,y,a,b,k,i;

    bool operator <(const data&t) const

    {

        return k<t.k||k==t.k&&b<t.b;

    }

}e[M],a[N],undo[N];

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

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4537.in","r",stdin);

    freopen("bzoj4537.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();

    int block=sqrt(m);

    for (int i=;i<=m;i++) e[i].x=read(),e[i].y=read(),e[i].a=read(),e[i].b=read(),e[i].k=e[i].a;

    sort(e+,e+m+);

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

    {

        e[i].k=(i-)/block,mx[(i-)/block]=max(mx[(i-)/block],e[i].a),R[(i-)/block]=max(R[(i-)/block],i);

        if ((i-)%block==) L[(i-)/block]=i;

    }

    cnt=(m-)/block+;mx[cnt]=inf+;R[cnt]=-;

    sort(e+,e+m+);

    q=read();

    for (int i=;i<=q;i++)

    {

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

        for (int j=;j<=cnt;j++) if (a[i].a<mx[j]) {a[i].k=j;break;}

    }

    sort(a+,a+q+);

    int x=;

    for (int i=;i<=cnt;i++)

    {

        for (int i=;i<=n;i++) fa[i]=i,size[i]=;

        memset(mxa,,sizeof(mxa));

        memset(mxb,,sizeof(mxb));

        for (int j=;j<i;j++) cur[j]=L[j]-;

        while (x<q&&a[x+].k==i)

        {

            x++;

            for (int j=;j<i;j++)

            while (e[cur[j]+].k==j&&e[cur[j]+].b<=a[x].b)

            {

                cur[j]++;

                int p=find(e[cur[j]].x),q=find(e[cur[j]].y);

                if (size[p]<size[q]) swap(p,q);

                if (p!=q) size[p]+=size[q];

                fa[q]=p;mxa[p]=max(max(mxa[p],mxa[q]),e[cur[j]].a),mxb[p]=max(max(mxb[p],mxb[q]),e[cur[j]].b);

            }

            int top=;

            for (int j=L[i];j<=R[i];j++)

            {

                if (e[j].b>a[x].b) break;

                if (e[j].a<=a[x].a)

                {

                    int p=find(e[j].x),q=find(e[j].y);

                    if (size[p]<size[q]) swap(p,q),swap(e[j].x,e[j].y);

                    top++;undo[top].x=q,undo[top].i=size[p];

                    undo[top].y=p,undo[top].a=mxa[p],undo[top].b=mxb[p];

                    if (p!=q) size[p]+=size[q];

                    fa[q]=p;mxa[p]=max(max(mxa[p],mxa[q]),e[j].a),mxb[p]=max(max(mxb[p],mxb[q]),e[j].b);

                }

            }

            if (find(a[x].x)==find(a[x].y)&&mxa[find(a[x].x)]==a[x].a&&mxb[find(a[x].x)]==a[x].b) ans[a[x].i]=;

            for (;top;top--)

            {

                mxa[undo[top].y]=undo[top].a,mxb[undo[top].y]=undo[top].b;

                fa[undo[top].x]=undo[top].x;size[undo[top].y]=undo[top].i;

            }

        }

    }

    for (int i=;i<=q;i++) printf(ans[i]?"Yes\n":"No\n");

    return ;

}

巴特西

BZOJ4537 HNOI2016最小公倍数（莫队+并查集）

最新文章

热门文章