【题解】[HNOI2016] 最小公倍数 LuoguP3247 —Qiuly

我写的好丑，跑的巨慢（

震惊，块大小 $\sqrt{m\log n}$ 跑的飞快，而 $\sqrt{m}$ 却慢得离谱，这究竟是道德的沦丧还是人性的扭曲！

很显然吧对于一对 $a,b$ ，将 $a’\leq a,b’\leq b$ 的边加进来后判断一下 $s,t$ 是否联通，连通块中是否有 $a’=a$ 的边，是否有 $b’=b$ 的边即可。

然后现在将一维从小到大排序 (当前维相等的话按照第二维从小到大排序)，依次加入边。

我选择将 $b$ 排序，那么现在不确定的就是 $a$ 。

考虑用分块维护 $a$ ，每一块维护一个并查集，存的就是当前块以及之前所有块的边形成的并查集。

加入一条边的时候就将当前块以及后面的块都连上边。

询问的时候显然是找到第一个小于询问的 $a$ 的右端点，然后往后暴力加上这些散块里面的边。

那就每个块的并查集都支持一下撤销即可，加边计算完答案后暴力撤销就好了。

块大小 $\sqrt{m}$ 被卡的死死的，可能是我写丑了（

inline bool cmpE1(Edge e1,Edge e2) {return e1.a==e2.a?e1.b<e2.b:e1.a<e2.a;}
inline bool cmpE2(Edge e1,Edge e2) {return e1.b==e2.b?e1.a<e2.a:e1.b<e2.b;}
inline bool cmpQ(Query q1,Query q2) {return q1.b==q2.b?q1.a<q2.a:q1.b<q2.b;}

int main() {
    IN(n),IN(m);
    for(int i=1;i<=m;++i) IN(G[i].u),IN(G[i].v),IN(G[i].a),IN(G[i].b),G[i].id=i;
    IN(q);
    for(int i=1;i<=q;++i) IN(Q[i].s),IN(Q[i].t),IN(Q[i].a),IN(Q[i].b),Q[i].id=i;

    sort(G+1,G+1+m,cmpE1);
    for(int i=1;i<=m;++i) G[i].rk=i,tmp[i]=G[i].a;
    sort(G+1,G+1+m,cmpE2);
    for(int i=1;i<=m;++i) pos[G[i].rk]=i;
    sort(Q+1,Q+1+q,cmpQ);

    int siz=sqrt(m*18),lim=0;
    for(int t=1,c=1;t<=m;t+=siz,++c,lim=c) {
        int now=min(t+siz-1,m);
        for(int i=t;i<=now;++i) bel[i]=c;
        nxt[c]=now;
    }
    --lim;

    int L=1;
    for(int i=1;i<=lim;++i)
        for(int j=1;j<=n;++j)
            dsu[i].fa[j]=j,dsu[i].siz[j]=1,
            dsu[i].va[j]=dsu[i].vb[j]=-1;

    for(int t=1;t<=q;++t) {
        while(L<=m&&G[L].b<=Q[t].b) {
            for(int t=bel[G[L].rk];t<=lim;++t)
                dsu[t].merge(G[L].u,G[L].v,G[L].a,G[L].b);
            use[G[L].rk]=true,++L;
        }
        int l=1,r=m,mid,res=0;
        while(l<=r) (tmp[mid=l+r>>1]<=Q[t].a)?(res=mid,l=mid+1):r=mid-1;
        int ID=bel[res]-1;
        if(ID<1) {ans[Q[t].id]=false;continue;}

        nowID=ID;
        for(int i=nxt[ID]+1;i<=res;++i) {
            if(G[pos[i]].a>Q[t].a) break;
            if(use[i]==true)
                dsu[ID].Merge(G[pos[i]].u,G[pos[i]].v,G[pos[i]].a,G[pos[i]].b);
        }
        int _s=dsu[ID].find(Q[t].s),_t=dsu[ID].find(Q[t].t);
        ans[Q[t].id]=(bool)(_s==_t&&dsu[ID].va[_s]==Q[t].a&&dsu[ID].vb[_s]==Q[t].b);
        back();
    }
    for(int i=1;i<=q;++i) puts(ans[i]==1?"Yes":"No");
    return 0;
}