题目
题目链接：https://www.luogu.com.cn/problem/P4899
在日本的茨城县内共有 (N) 个城市和 (M) 条道路。这些城市是根据人口数量的升序排列的，依次编号为 (0) 到 (N - 1)。每条道路连接两个不同的城市，并且可以双向通行。由这些道路，你能从任意一个城市到另外任意一个城市。
你计划了 (Q) 个行程，这些行程分别编号为 (0) 至 (Q - 1)。第 (i(0 leq i leq Q - 1)) 个行程是从城市 (S_i) 到城市 (E_i)。
你是一个狼人。你有两种形态：人形和狼形。在每个行程开始的时候，你是人形。在每个行程结束的时候，你必须是狼形。在行程中，你必须要变身（从人形变成狼形）恰好一次，而且只能在某个城市内（包括可能是在 (S_i) 或 (E_i) 内）变身。
狼人的生活并不容易。当你是人形时，你必须避开人少的城市，而当你是狼形时，你必须避开人多的城市。对于每一次行程 (i(0 leq i leq Q - 1))，都有两个阈值 (L_i) 和 (R_i(0 leq L_i leq R_i leq N - 1))，用以表示哪些城市必须要避开。准确地说，当你是人形时，你必须避开城市 (0, 1, ldots , L_i - 1) ；而当你是狼形时，则必须避开城市 (R_i + 1, R_i + 2, ldots , N - 1)。这就是说，在行程 (i) 中，你必须在城市 (L_i, L_i + 1, ldots , R_i) 中的其中一个城市内变身。
你的任务是，对每一次行程，判定是否有可能在满足上述限制的前提下，由城市 (S_i) 走到城市 (E_i)。你的路线可以有任意长度。
思路
对于一组询问，我们求出在人形和狼形的时候分别可以到达的点集，然后判断一下有无交即可。
我们设边权为连接的两个点的较小点权，求出其 kruskal 生成树，那么对于一次询问，在狼形的时候可以走的点集就是其中一个点为根的子树。同理可以设边权为较大点权，其 kruskal 生成树中的一个子树为在人形时可以走的点集。
求出两棵 kruskal 生成树之后，对于一组询问 (s,t,l,r)，我们可以通过倍增找出 (s) 和 (t) 分别在两棵树中的一个祖先节点，满足这个祖先节点的权值在可以走的范围内且深度较小。那么这两个节点的子树就是可以走的点权。
求出两棵树的 dfs 序，我们需要判断的就是两个 dfs 序的两个区间是否有交。我们以其中一棵树的 dfs 序建立可持久化线段树，以另一棵树的 dfs 序作为下标。询问时就直接判断第一个区间的可持久化线段树内，值域在第二个区间的和是否为 (0) 即可。
时间复杂度 (O((m+Q)log n))。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=400010,LG=20;
int n,m,Q,rt[N];
struct edge1
{
int u,v;
}e1[N];
bool cmp1(edge1 x,edge1 y)
{
return max(x.u,x.v)<max(y.u,y.v);
}
bool cmp2(edge1 x,edge1 y)
{
return min(x.u,x.v)>min(y.u,y.v);
}
struct Kruscal
{
int tot,father[N],val[N],head[N],rk[N],dfn[N],size[N],dep[N],f[N][LG+1];
struct edge2
{
int next,to;
}e[N];
void add(int from,int to)
{
e[++tot]=(edge2){head[from],to};
head[from]=tot;
}
int find(int x)
{
return x==father[x]?x:father[x]=find(father[x]);
}
void kruskal(int id)
{
memset(head,-1,sizeof(head));
if (id==1) sort(e1+1,e1+1+m,cmp1);
else sort(e1+1,e1+1+m,cmp2);
for (int i=1;i<=n*2;i++) father[i]=i;
int num=n;
for (int i=1;i<=m;i++)
{
int x=find(e1[i].u),y=find(e1[i].v);
if (x!=y)
{
num++;
if (id==1) val[num]=max(e1[i].u,e1[i].v);
else val[num]=min(e1[i].u,e1[i].v);
add(num,x); add(num,y);
father[x]=father[y]=num;
}
}
}
int dfs(int x,int fa)
{
dep[x]=dep[fa]+1; f[x][0]=fa;
rk[x]=++tot; dfn[tot]=x; size[x]=1;
if (!val[x]) val[x]=val[fa];
for (int i=1;i<=LG;i++)
f[x][i]=f[f[x][i-1]][i-1];
for (int i=head[x];~i;i=e[i].next)
size[x]+=dfs(e[i].to,x);
return size[x];
}
int binary(int x,int l,int r)
{
for (int i=LG;i>=0;i--)
if (val[f[x][i]]>=l && val[f[x][i]]<=r) x=f[x][i];
return x;
}
}t1,t2;
struct SegTree
{
int tot,lc[N*LG*4],rc[N*LG*4],sum[N*LG*4];
int ins(int now,int l,int r,int k)
{
int x=++tot;
lc[x]=lc[now]; rc[x]=rc[now]; sum[x]=sum[now]+1;
if (l==r) return x;
int mid=(l+r)>>1;
if (k<=mid) lc[x]=ins(lc[now],l,mid,k);
else rc[x]=ins(rc[now],mid+1,r,k);
return x;
}
int query(int nowl,int nowr,int l,int r,int ql,int qr)
{
if (l==ql && r==qr)
return sum[nowr]-sum[nowl];
int mid=(l+r)>>1;
if (qr<=mid) return query(lc[nowl],lc[nowr],l,mid,ql,qr);
if (ql>mid) return query(rc[nowl],rc[nowr],mid+1,r,ql,qr);
return query(lc[nowl],lc[nowr],l,mid,ql,mid)+query(rc[nowl],rc[nowr],mid+1,r,mid+1,qr);
}
}seg;
int main()
{
scanf("%d%d%d",&n,&m,&Q);
for (int i=1;i<=m;i++)
{
scanf("%d%d",&e1[i].u,&e1[i].v);
e1[i].u++; e1[i].v++;
}
t1.kruskal(1); t2.kruskal(2);
t1.tot=t2.tot=0;
for (int i=1;i<=2*n;i++)
{
if (t1.find(i)==i) t1.dfs(i,0);
if (t2.find(i)==i) t2.dfs(i,0);
}
for (int i=1;i<=n*2;i++)
if (t2.dfn[i]<=n) rt[i]=seg.ins(rt[i-1],1,n*2,t1.rk[t2.dfn[i]]);
else rt[i]=rt[i-1];
while (Q--)
{
int s,t,l,r;
scanf("%d%d%d%d",&s,&t,&l,&r);
s=t2.binary(s+1,l+1,n); t=t1.binary(t+1,1,r+1);
int p=seg.query(rt[t2.rk[s]-1],rt[t2.rk[s]+t2.size[s]-1],1,n*2,t1.rk[t],t1.rk[t]+t1.size[t]-1);
printf("%d
",(bool)p);
}
return 0;
}