题目id:15724
题意
给定 n 个点，从左到右按顺序排成一行。连接第 i 个点和第 i+1 个点无向边，需要拥有类型为 C_i 的钥匙。到达第 i 个点可以得到 B_i 把钥匙，分别为 A[i][1],A[i][2],\dots,A[i][B_i] 有 Q 个询问回答能否从起始点 X_i 到结束点 Y_i ，能则输出 YES 不能则输出 NO
其中 2≤N≤5×10^5,1≤Q≤5×10^5
思路
观察到 Q 很大，所以可以离线做，对于每个点 X_i 求出可达区间 [L_i,R_i]
考虑可达区间扩展：
\quad 对每个点 i 求出 bef_{c[i]} 和 nxt_{c[i]} 分别表示在点 i 前面或后面，距离点 i 最近的拥有类型 C_i 钥匙的点位置
-
当前区间为 [L_i,R_i] 时 若 L_i \leq nxt_{c[L_i-1]} \leq R_i 则代表可以扩展到 [L_i-1,R_i]
-
当前区间为 [L_i,R_i] 时 若 L_i \leq bef_{c[R_i]} \leq R_i 则代表可以扩展到 [L_i,R_i+1]
但是发现若当前点 i 能够到达点 j 那么，区间 [L_j,R_j] 内的点，点 i 都可达所以每扩展到一个点让 L_i=min(L_i,L_j) \quad R_i=max(R_i,R_j)
用递归求解使每个点只用扩展一次跑的较快
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=5e5+100;
int c[N],n,B[N];
int L[N],R[N],bef[N],nxt[N],rem[N],q,vis[N];
vector<int>A[N];
void dfsf(int pos){
if(vis[pos])return;
vis[pos]=1;
int flag=1;
while(flag){
flag=0;
while(L[pos]-1>=1&&nxt[L[pos]-1]>=L[pos]&&nxt[L[pos]-1]<=R[pos]){
dfsf(L[pos]-1);
flag=1;L[pos]=min(L[L[pos]-1],L[pos]);
R[pos]=max(R[L[pos]-1],R[pos]);
}
while(R[pos]+1<=n&&bef[R[pos]]>=L[pos]&&bef[R[pos]]<=R[pos]){
dfsf(R[pos]+1);
flag=1;L[pos]=min(L[R[pos]+1],L[pos]);
R[pos]=max(R[pos],R[R[pos]+1]);
}
}
return;
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++)scanf("%d",&c[i]);
for(int i=1;i<=n;i++){
scanf("%d",&B[i]);
for(int j=1;j<=B[i];j++){
int x;
scanf("%d",&x);
A[i].push_back(x);
rem[x]=i;
}
bef[i]=rem[c[i]];
}
for(int i=1;i<=n;i++)rem[i]=n+1;
for(int i=n;i>=1;i--){
for(int j=0;j<B[i];j++)
rem[A[i][j]]=i;
nxt[i-1]=rem[c[i-1]];L[i]=R[i]=i;
}
for(int i=1;i<=n;i++)
if(!vis[i])dfsf(i);
scanf("%d",&q);
for(int i=1;i<=q;i++){
int x,y;
scanf("%d%d",&x,&y);
if(y>=L[x]&&y<=R[x])printf("YES\n");
else printf("NO\n");
}
return 0;
}