Luogu4899 狼人

题面

简化题意

给定一个无向图，$q$ 组询问。每次询问是否存在一条路径 $s\rightarrow t$，满足先只走编号不小于 $l$ 的节点，后只走编号不大于 $r$ 的节点。

$n,q\leq 2\times 10^5,m\leq 4\times 10^5$，强制在线。

题解

如果可以求出从 $s$ 出发，只走编号不小于 $l$ 的节点能到达的点集 $A$，和从 $t$ 出发只走编号不大于 $r$ 的节点能到达的点集 $B$。那么每组询问就相当于问你 $A,B$ 的交集是否不为空。

先考虑如何快速求出一个点 $s$ 只走编号不小于 $l$ 的节点能到达的点集，不难发现这是一个 kruskal 重构树的形式。把一条边的边权视为两个节点编号的较大值，建最小生成树，使得 $u,v$ 两点路径中最大节点编号的最小值为 $\operatorname{LCA}(u,v)$，则用倍增的方法，可以快速找到 $u$ 点经过节点编号不超过 $k$ 的点能到达的点集，应该是某个节点的子树。同理把一条边的边权视为两节点编号的较小值，建最大生成树，可以使得 $u,v$ 两点路径中最小节点编号的最大值为 $\operatorname{LCA}(u,v)$，用倍增的方法可以快速找到 $u$ 点经过节点编号不小于 $k$ 的点能到达的点集，也是某个点的子树。

因此对于一组 $s,t,l,r$，可以用倍增的方法快速找到 $s,t$ 按各自规则分别能走到的点集，而且这个点集在重构树上对应的是两个重构树上的子树。

建立重构树后，问题转化为：对于两个树，分别给定一个子树，求这两个子树的交集是否不为空。

我们发现一个子树内的 $dfn$ 一定是连续的，因此又可以利用 $dfn$ 把子树判交的问题转化为序列判交的问题。

设一个节点 $i$ 在两个重构树上的 $dfn$ 分别为 $a_i,b_i$，询问对应的子树的 $dfn$ 区间分别为 $[l_1,r_1],[l_2,r_2]$，问题转化为：求是否存在点 $x$，使得 $a_x\in[l_1,r_1],b_x\in[l_2,r_2]$。

把 $a_i,b_i$ 当作平面直角坐标系上的一个点 $(a_i,b_i)$，问题转化为求一个左上角为 $(l_1,l_2)$，右下角为 $(r_1,r_2)$ 的矩形内是否有点。

KDTree 数点即可完成。当然也可以使用树套树，不推荐用树状数组、CDQ 等离线算法（虽然洛谷上能过，但个人觉得还是尊重下原题的强制在线）。

一个简单的 Trick：本题没有修改操作，可以提前 build 好，不需要写重构；而且判定时只需要看有没有点，不需要数有几个点，所以发现有点就立刻 return。码量和效率都有大幅度改进。（注：从可能 TLE 4.2s 变成了最慢的点 900ms。）

代码

#include<bits/stdc++.h>
using namespace std;
const int max_n=400005;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
struct graph{
    int hd[max_n],nx[max_n*2],to[max_n*2],ct;
    graph(){ct=1;}
    inline void add(int u,int v){
        nx[++ct]=hd[u],hd[u]=ct,to[ct]=v;
    }
}t[2],e;

int n,m,q,fa[2][max_n][22];

struct UnionFind{
    int fa[max_n];
    inline void init(){
        for(register int i=1;i<=n*2;++i)
            fa[i]=i;
    }
    inline int find(int x){
        if(fa[x]==x) return x;
        return fa[x]=find(fa[x]);
    }
    inline void merge(int x,int y){
        fa[x]=y;
    }
}uf;

int L[2][max_n],R[2][max_n],cntd; // 重构树上一点子树对应的 dfn 区间

inline void dfs(int tp,int u){
    L[tp][u]=++cntd;
    for(register int i=1;i<=20;++i)
        fa[tp][u][i]=fa[tp][fa[tp][u][i-1]][i-1];
    for(register int i=t[tp].hd[u];i;i=t[tp].nx[i]){
        int v=t[tp].to[i];
        if(v==fa[tp][u][0]) continue;
        dfs(tp,v);
    }
    R[tp][u]=cntd;
}

inline int find(int tp,int x,int p){ // 倍增找点集对应的子树的根
    if(tp){
        for(register int i=20;i>=0;--i)
            if(fa[1][x][i]<=p)
                x=fa[1][x][i];
        return x;
    }
    for(register int i=20;i>=0;--i)
        if(fa[0][x][i]>=p)
            x=fa[0][x][i];
    return x;
}

inline void krul(int tp){
    uf.init(),cntd=0;int tot=1;
    if(!tp){ // 分两种方法建重构树
        for(register int u=n;u>=1;--u)
            for(register int i=e.hd[u];i && tot<n;i=e.nx[i]){
                int v=e.to[i];
                int fu=uf.find(u),fv=uf.find(v);
                if(fu==fv || v<u) continue;
                uf.merge(fv,fu);
                t[0].add(fu,fv);
                fa[0][fv][0]=fu,
                ++tot;
            }
        fa[0][1][0]=1;
        dfs(0,1);
    }
    else{
        for(register int u=1;u<=n;++u)
            for(register int i=e.hd[u];i && tot<n;i=e.nx[i]){
                int v=e.to[i];
                int fu=uf.find(u),fv=uf.find(v);
                if(fu==fv || v>u) continue;
                uf.merge(fv,fu);
                t[1].add(fu,fv);
                fa[1][fv][0]=fu,
                ++tot;
            }
        fa[1][n][0]=n;
        dfs(1,n);
    }
}

struct point{
    int x,y;
}pos[max_n];
inline point makep(int a,int b){
    point res;
    res.x=a,res.y=b;
    return res;
}
bool cmpt=0;
inline bool cmp(point i,point j){
    if(cmpt) return i.x<j.x;
    return i.y<j.y;
}

struct KD_Tree{
    struct dot{
        point l,r;
    }a[max_n*4];
    int L[max_n*4],R[max_n*4];
    #define ls(x) (x<<1)
    #define rs(x) (x<<1|1)

    inline void pushup(int x){
        a[x].l.x=min(a[ls(x)].l.x,a[rs(x)].l.x),a[x].r.x=max(a[ls(x)].r.x,a[rs(x)].r.x);
        a[x].l.y=min(a[ls(x)].l.y,a[rs(x)].l.y),a[x].r.y=max(a[ls(x)].r.y,a[rs(x)].r.y);
    }
    inline void build(int x,int l,int r,int t){
        L[x]=l,R[x]=r;
        if(l==r){
            a[x].l=a[x].r=pos[l];
            return;
        }
        int mid=(l+r)>>1;
        cmpt=t;
        nth_element(pos+l,pos+mid,pos+r+1,cmp);
        build(ls(x),l,mid,t^1);
        build(rs(x),mid+1,r,t^1);
        pushup(x);
    }
    inline bool ask(int x,point i,point j){
        if(!x || a[x].l.x>j.x || a[x].r.x<i.x || a[x].l.y>j.y || a[x].r.y<i.y)
            return 0;
        if(a[x].l.x>=i.x && a[x].r.x<=j.x && a[x].l.y>=i.y && a[x].r.y<=j.y)
            return 1;
        if(L[x]==R[x])
            return 0;
        return ask(ls(x),i,j)||ask(rs(x),i,j);
    }
}kdt;

signed main(){
	n=read(),m=read(),q=read();
	for(register int i=1;i<=m;++i){
	    int u=read()+1,v=read()+1;
	    e.add(u,v),e.add(v,u);
	}
	krul(0),krul(1);
	for(register int i=1;i<=n;++i)
	    pos[i]=makep(L[0][i],L[1][i]);
	kdt.build(1,1,n,0);
	while(q--){
	    int x=read()+1,y=read()+1,l=read()+1,r=read()+1;
	    x=find(0,x,l),y=find(1,y,r);
        write(kdt.ask(1,makep(L[0][x],L[1][y]),makep(R[0][x],R[1][y]))),putchar('\n');
	}
	return 0;
}