Luogu

BZOJ

分析

对于每个询问 $(u,v,A,B)$,显然只能走 $a\leq A,b\leq B$ 的边。

然后有一个很套路的方法 我不会。为了方便,下面设询问的 $a$ 和 $b$ 为 $A$ 和 $B$。

将所有边按 $a$ 排序并分块,将所有询问按 $b$ 排序。

设第 $i$ 块的左右端点为 $[l_i,r_i]$ ,找出所有 $A\in [a_{l_i},a_{r_i})$ 的询问,然后一个个处理。

对于第 $j$ 个询问,有两种边对它有贡献:

  • 前 $i-1$ 块中满足 $b\leq B_j$ 的边。显然排序后 $B_j$ 是单调递增的,于是可以将前 $i-1$ 块按 $b$ 排序,然后用一个指针来维护。
  • 第 $i$ 块中满足 $a\leq A_j,b\leq B_j$ 的边。这种边最多只有根号条,可以暴力来搞。

注意到可能会存在一些满足之前的询问,但是不满足现在的询问的边,而并不能每次重建并查集。于是用一个资瓷撤销的并查集来维护即可。

另外,据说块大小为 $\sqrt{m\log n}$ 时最快。

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline void chkmax(int& x,int y) { if (y>x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

struct Edge { int u,v,a,b; } e[N];
struct Query { int u,v,a,b,id; } q[N],o[N];
struct node { int u,v,a,b,sz; } sta[N];

inline int cmp1(Edge a,Edge b) { return a.a==b.a?a.b<b.b:a.a<b.a; }
inline int cmp2(Edge a,Edge b) { return a.b==b.b?a.a<b.a:a.b<b.b; }
inline int cmp3(Query a,Query b) { return a.b==b.b?a.a<b.a:a.b<b.b; }

int n,m,Q,top;
int ans[N];

struct UFS {
    int f[N],A[N],B[N],sz[N];
    inline void init(int n) {
        for (re int i=1;i<=n;++i) f[i]=i,A[i]=B[i]=-1,sz[i]=1;
    }
    inline int find(int x) { return x==f[x]?x:find(f[x]); }
    inline void merge(int x,int y,int a,int b) {
        x=find(x),y=find(y); if (sz[x]>sz[y]) swap(x,y);
        sta[++top]=(node){x,y,A[y],B[y],sz[y]};
        if (x!=y) f[x]=y,sz[y]+=sz[x],chkmax(A[y],A[x]),chkmax(B[y],B[x]);
        chkmax(A[y],a),chkmax(B[y],b);
    }
} S;

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) e[i]=(Edge){read(),read(),read(),read()};
    Q=read();
    for (re int i=1;i<=Q;++i) q[i]=(Query){read(),read(),read(),read(),i};
    sort(e+1,e+m+1,cmp1); sort(q+1,q+Q+1,cmp3);
    for (re int i=1,sz=sqrt(m*log2(n));i<=m;i+=sz) {
        S.init(n); int sum=0;
        for (re int j=1;j<=Q;++j)
            if (e[i].a<=q[j].a&&(q[j].a<e[i+sz].a||i+sz>m))
                o[++sum]=q[j];
        if (!sum) continue;
        if (i!=1) sort(e+1,e+i,cmp2);
        for (re int j=1,k=1;j<=sum;++j) {
            //第一类
            while (k<i&&e[k].b<=o[j].b) {
                S.merge(e[k].u,e[k].v,e[k].a,e[k].b);
                ++k;
            }
            //第二类
            top=0;
            for (re int l=i;l<i+sz&&l<=m;++l)
                if (e[l].a<=o[j].a&&e[l].b<=o[j].b)
                    S.merge(e[l].u,e[l].v,e[l].a,e[l].b);
            int u=S.find(o[j].u),v=S.find(o[j].v);
            if (u==v&&S.A[u]==o[j].a&&S.B[u]==o[j].b) ans[o[j].id]=1;
            else ans[o[j].id]=0;
            //撤销
            while (top) {
                int u=sta[top].u,v=sta[top].v; S.f[u]=u;
                S.A[v]=sta[top].a,S.B[v]=sta[top].b,S.sz[v]=sta[top].sz;
                --top;
            }
        }
    }
    for (re int i=1;i<=Q;++i) puts(ans[i]?"Yes":"No");
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 16 PM