【题目】
原题地址
给定一幅无向图，多次询问从Si出发到Ti，是否存在一条路径Si−>x−>Ti，满足Si−>x经过的点编号≤x，x−>Ti经过的点的编号≥x，Li≤x≤Ri，数字级别2×105
【解题思路】
这题实际上有点类似NOI2018的D1T1，只不过这题的限制已经在点上了。
仍然考虑重构树，我们需要构建一棵树，使得任意一个非根节点的标号都比它的父亲大。
我们只需要从大到小枚举一个点x，尝试将它加入树中，枚举所有与它相邻且编号比它大的节点y，如果二者不在一个连通块中，就让y的并查集的根成为x的儿子，再在并查集中连起来。
那么现在从S出发只走大于等于Li的节点能到的所有点，在树上对应了一个子树。我们可以用树上倍增找到这个子树。
同理从小到大再做一次，可以得到从T出发只走小于等于Ri的节点能到的所点也对应了一个子树。
用dfs序可以转化为区间问题，那么现在的问题就是在这两个区间中是否同时拥有某个元素。
这里每个元素在一个序列中都恰好只出现了一次，我们只需要将一个元素在两个dfs序中出现的位置p1,p2看作一个二维数点，即(p1,p2)，那么问题就转化为了判断平面内一个矩形中是否有点，这是一个经典问题，离线BIT即可。
时间复杂度O(nlogn)
【参考代码(交互格式)】
#include "werewolf.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
#define vi vector<int>
#define lowbit(x) (x&(-x))
using namespace std;
typedef pair<int,int> pii;
const int N=4e5+10,M=19;
int n,m,q,cnt,tot;
int head[N],pos[N],fa[N],ans[N],tr[N<<1];
int dfn[2][N],siz[2][N],f1[M][N],f2[M][N],c1[M][N],c2[M][N];
pii rd[N<<1];
struct Tway{int u,v;}e[N];
struct Tline{int id,l,r,c;};
vi Tans;
vector<Tline>line[N];
bool cmp1(const Tway&A,const Tway&B){return min(A.u,A.v)>min(B.u,B.v);}
bool cmp2(const Tway&A,const Tway&B){return max(A.u,A.v)<max(B.u,B.v);}
void add(int u,int v){rd[++tot]=mkp(v,head[u]);head[u]=tot;}
void dfs(int x,int tp)
{
if(x<n) dfn[tp][x]=++dfn[tp][cnt],siz[tp][x]=1;
//printf("%d %d\n",x,siz[tp][x]);
for(int i=head[x];i;i=rd[i].se)
{
int v=rd[i].fi; dfs(v,tp);
if(!dfn[tp][x]) dfn[tp][x]=dfn[tp][v];
siz[tp][x]+=siz[tp][v];
}
}
int findf(int x){return fa[x]==x?x:fa[x]=findf(fa[x]);}
void update(int x){for(;x<=n;x+=lowbit(x))tr[x]++;}
int query(int x){int ret=0;for(;x;x-=lowbit(x))ret+=tr[x];return ret;}
vi check_validity(int P,vi X,vi Y,vi S,vi E,vi L,vi R)
{
n=P;m=X.size();q=S.size();
for(int i=0;i<m;++i) e[i].u=X[i],e[i].v=Y[i];
for(int i=0;i<n<<1;++i) fa[i]=i;
memset(head,0,sizeof(head));tot=0;cnt=n; sort(e,e+m,cmp1);
for(int i=0;i<m;++i)
{
int fu=findf(e[i].u),fv=findf(e[i].v);
//printf("%d %d %d %d\n",e[i].u,e[i].v,fu,fv);
if(fu^fv)
{
add(cnt,fu);add(cnt,fv);
f1[0][fu]=f1[0][fv]=cnt;c1[0][fu]=c1[0][fv]=min(e[i].u,e[i].v);
fa[fu]=fa[fv]=cnt++;
}
}
dfs(cnt-1,0);
for(int i=1;i<18;++i) for(int j=0;j<cnt;++j) if(f1[i-1][j])
f1[i][j]=f1[i-1][f1[i-1][j]],c1[i][j]=c1[i-1][f1[i-1][j]];
for(int i=0;i<n<<1;++i) fa[i]=i;
memset(head,0,sizeof(head));tot=0;cnt=n; sort(e,e+m,cmp2);
for(int i=0;i<m;++i)
{
int fu=findf(e[i].u),fv=findf(e[i].v);
//printf("%d %d %d %d\n",e[i].u,e[i].v,fu,fv);
if(fu^fv)
{
add(cnt,fu);add(cnt,fv);
f2[0][fu]=f2[0][fv]=cnt;c2[0][fu]=c2[0][fv]=max(e[i].u,e[i].v);
fa[fu]=fa[fv]=cnt++;
}
}
dfs(cnt-1,1);
for(int i=1;i<18;++i) for(int j=0;j<cnt;++j) if(f2[i-1][j])
f2[i][j]=f2[i-1][f2[i-1][j]],c2[i][j]=c2[i-1][f2[i-1][j]];
for(int i=0,x,y;i<q;++i)
{
x=S[i];y=L[i];
for(int j=17;~j;--j) if(f1[j][x] && c1[j][x]>=y) x=f1[j][x];
int l1=dfn[0][x],r1=l1+siz[0][x]-1;
x=E[i];y=R[i];
for(int j=17;~j;--j) if(f2[j][x] && c2[j][x]<=y) x=f2[j][x];
int l2=dfn[1][x],r2=l2+siz[1][x]-1;
line[l1-1].pb((Tline){i,l2,r2,-1});
line[r1].pb((Tline){i,l2,r2,1});
//printf("%d %d %d %d\n",l1,r1,l2,r2);
}
for(int i=0;i<n;++i) pos[dfn[0][i]]=dfn[1][i];
for(int i=1;i<=n;++i)
{
//printf("%d %d\n",i,pos[i]);
update(pos[i]);
int sz=line[i].size();
for(int j=0;j<sz;++j) ans[line[i][j].id]+=line[i][j].c*(query(line[i][j].r)-query(line[i][j].l-1));
}
for(int i=0;i<q;++i) Tans.pb((bool)ans[i]);
return Tans;
}
【总结】
套路啊套路。