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

· · 题解

分块 + 并查集启发式合并

思路很简单,就是找到所有a,b都小于等于某个询问的边然后并查集合并,维护每个集合的a,b的最大值看是否等于询问的a,b.

直接暴力显然会超时,于是考虑分块,显然分成根号n块.

先整体把边按a排序,询问先读进来后按b排序,然后对于每一块的边按b排序,然后进行并查集的合并操作

值得注意的是,由于要撤销操作(分块处理,处理完一块后要“处理作案痕迹”)故这里的并查集不能使用压缩路径,否则难以实现撤销undo操作,而只能使用并查集的启发式合并,即按秩合并(这样子的话效率似乎是均摊O(lgn)？？？)并记录操作,然后撤销即可.

PS:这题本来4s时限结果LG上一开始是1s时限卡了我几次....

又臭又长的代码如下:

/*
    Programed By Harry·Shaun·Wang
    2016.12.4 
*/
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#define MAXN 50005
#define MAXM 100005
#define MAXQ 50005
#define union Union
using namespace std;
inline int getint()
{
    int x=0;
    char c=getchar();
    while(c<'0' || c>'9') c=getchar();
    while(c>='0' && c<='9')
    {
        x=x*10+c-48;
        c=getchar();
    }
    return x;
}
struct Edge
{
    int from,to;
    int a,b;
    int index;
    Edge& input(int i)
    {
        from=getint(),to=getint();
        a=getint(),b=getint();
        index=i;
        return *this;
    }
};
struct Operation
{
    int from,to;
    int father,size;
    int maxa,maxb;
};
int n,m,q,l;
Edge E[MAXM],Q[MAXQ],S[MAXN];
Operation O[MAXQ];
int f[MAXN],size[MAXN];
int maxa[MAXN],maxb[MAXN];
int top,sum;
int ans[MAXQ];
inline bool cmpa(const Edge &x,const Edge &y)
{
    if(x.a!=y.a) return x.a<y.a;
    else return x.b<y.b;
}
inline bool cmpb(const Edge &x,const Edge &y)
{
    if(x.b!=y.b) return x.b<y.b;
    else return x.a<y.a;
}
inline int max(int a,int b,int c)
{
    if(a<b) a=b;
    if(a<c) a=c;
    return a;
}
inline int find(int x)
{
    while(x!=f[x]) x=f[x];
    return x;
}
inline void union(int x,int y,int a,int b)
{
    x=find(x),y=find(y);
    if(size[x]>size[y]) swap(x,y);
    ++sum;
    O[sum].from=x,O[sum].to=y;
    O[sum].maxa=maxa[y],O[sum].maxb=maxb[y];
    O[sum].father=f[x],O[sum].size=size[y];
    if(x==y)
    {
        maxa[x]=max(maxa[x],a); 
        maxb[x]=max(maxb[x],b); 
        return;
    }
    f[x]=y;
    size[y]+=size[x];
    maxa[y]=max(maxa[x],maxa[y],a);
    maxb[y]=max(maxb[x],maxb[y],b);
}
inline void undo()
{
    while(sum) 
    {
        f[O[sum].from]=O[sum].father; 
        size[O[sum].to]=O[sum].size;
        maxa[O[sum].to]=O[sum].maxa;
        maxb[O[sum].to]=O[sum].maxb;
        --sum;
    }
}
int main()
{
    n=getint(),m=getint();
    for(int i=1; i<=m; ++i) E[i].input(i);
    q=getint();
    for(int i=1; i<=q; ++i) Q[i].input(i);
    stable_sort(E+1,E+m+1,cmpa),stable_sort(Q+1,Q+q+1,cmpb);
    l=sqrt(m);
    for(int i=1; i<=m; i+=l)
    {
        top=0;
        for(int j=1; j<=q; ++j)
            if(Q[j].a>=E[i].a && (i+l>m || Q[j].a<E[i+l].a))
                S[++top]=Q[j];
        stable_sort(E+1,E+i,cmpb);
        for(int j=1; j<=n; ++j)
        {
            f[j]=j;
            size[j]=1;
            maxa[j]=maxb[j]=-1;
        }
        for(int j=1,k=1; j<=top; ++j)
        {
            for(; k<i && E[k].b<=S[j].b; ++k)
                union(E[k].from,E[k].to,E[k].a,E[k].b);
            sum=0;
            for(int o=i; o<i+l && o<=m; ++o)
                if(E[o].a<=S[j].a && E[o].b<=S[j].b)
                    union(E[o].from,E[o].to,E[o].a,E[o].b);
            int x=find(S[j].from),y=find(S[j].to);
            ans[S[j].index]=(x==y && maxa[x]==S[j].a && maxb[x]==S[j].b);
            undo();
        }
    }
    for(int i=1; i<=q; ++i)
        if(ans[i]) puts("Yes");
        else puts("No");
    return 0;
}