题解

题意重述：$N$ 个房间排成一行，相邻房间 $i\leftrightarrow i{+}1$ 的门需要钥匙类型 $C_i$ 才能通过。进入某房间即可捡起该房间内的全部钥匙（可重复使用、不会消耗）。每次询问从房间 $x$ 空手出发（但可先拿 $x$ 房间的钥匙），问能否到达房间 $y$。

核心等价：设目标区间为 $[L,R]=[\min(x,y),\max(x,y)]$。若对区间内每一扇门 $i\in[L, R{-}1]$，在 $[L,R]$ 内至少有一个房间放有钥匙 $C_i$，则一定可以仅在区间内部完成拿钥匙与开门，最终到达目标端点；若存在某扇门在区间内完全没有对应钥匙，则必然不可达，答案为 $\texttt{NO}$。

就近钥匙位置预处理：

• 自右向左扫，得到 $R[i]$ 表示“从 $i$ 向右第一个（含 $i$）拥有钥匙 $C_i$ 的房间编号”，若不存在记为 $N{+}1$。
• 自左向右扫，得到 $L[i]$ 表示“从 $i$ 向左第一个（含 $i$）拥有钥匙 $C_{i-1}$ 的房间编号”，若不存在记为 $0$。

离线判定 $x<y$ 的可达性（右向）：把门的“边界”记作 $t\in( x, y ]$（对应门 $t{-}1$），只要在到达 $t$ 前能拿到一把 $C_{t-1}$ 的钥匙即可通过。拿钥匙的两种方式合并为一个充分条件：若存在某个位置 $i\in[x, t{-}1]$，其“向右最近能取到的钥匙区间”覆盖 $t$（即 $t\le R[i]$），且该门“向左最近钥匙位置”不在 $x$ 的左边（即 $L[t]\ge x$），则一定能在区间内完成这个门的开锁。

将充分条件转为“是否存在坏边界”的判定：

• 按左端点从小到大处理 $x=i=1\dots N$，维护一棵线段树，叶子对应边界 $t\in[1,N]$，保存 $\text{mnr}[t]=L[t]$；同时对所有 $t\le R[i]$ 的边界打上“当前左端点能覆盖到的最大 $i$ 值”$\text{mxl}[t]$：对区间 $[i{+}1, R[i]]$ 做区间取最大赋值 $\text{mxl}[t]\gets\max(\text{mxl}[t], i)$。
• 若在任意子区间内出现叶子满足 $\text{mxl}[t]\ge \text{mnr}[t]$，说明存在“坏边界”$t$：它只能依赖把钥匙拿到 $x$ 左边的位置（$L[t]\le i$），而“向右拿钥匙再回退”的覆盖也到达了该 $t$，两者冲突意味着该门在 $[x,y]$ 内没有可用钥匙，判为 $\texttt{NO}$。在线段树上用懒标记维护“是否存在 $\text{mxl}\ge \text{mnr}$ 的叶子”布尔值即可实现区间查询。
• 因为询问很多，把所有 $x<y$ 的询问按 $x$ 分桶，在扫描到 $i$ 时统一回答区间 $[i{+}1,y]$ 的布尔或值即可。

双向覆盖：为处理 $x>y$ 的询问，将整条链翻转（$p\mapsto N{+}1{-}p$、同时翻转门与钥匙列表）再做一遍同样的流程，合并两次结论。

复杂度：预处理 $L,R$ 为 $O(N+\sum B_i)$。每个 $i$ 做一次区间更新，每个询问做一次区间查询，总体 $O((N+Q)\log N)$，再翻转一遍仍同量级；空间 $O(N+\sum B_i)$。

//By smilemask
#include<bits/stdc++.h>
#include<ctime>
using namespace std;

namespace Smilemask{
#define rd read()
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int,int> PII;
#define debug(...) fprintf(stderr, __VA_ARGS__)

    inline int read(){
        int num=0,sign=1;char ch=getchar();
        while(!isdigit(ch)){if(ch=='-'){sign=-1;}ch=getchar();}
        while(isdigit(ch)) num=(num<<1)+(num<<3)+ch-'0',ch=getchar();
        return num*sign;
    }

    const int N=5e5+10;

    int n,m,col[N],L[N],R[N],ans[N];
    int X[N],Y[N];

    int tr[N*4],tag[N*4],mxl[N*4],mnr[N*4];
    vector<int> w[N];
    vector<PII> qr[N];

    #define ls(x) (x<<1)
    #define rs(x) (x<<1|1)

    void PushUp(int p){tr[p]|=(tr[ls(p)]|tr[rs(p)]);}

    void Mk(int p,int k){
        mxl[p]=max(mxl[p],k);tag[p]=max(tag[p],k);
        if(mxl[p]>=mnr[p])tr[p]=1;
    }

    void PushDown(int p){
        if(tag[p]!=-1)Mk(ls(p),tag[p]),Mk(rs(p),tag[p]),tag[p]=-1;
    }

    void Build(int l,int r,int p){
        mxl[p]=mnr[p]=tr[p]=0;tag[p]=-1;
        if(l==r){mnr[p]=L[l];return;}
        int mid=(l+r)>>1;
        Build(l,mid,ls(p));Build(mid+1,r,rs(p));
        mnr[p]=min(mnr[ls(p)],mnr[rs(p)]);
    }

    void Update(int nl,int nr,int l,int r,int p,int k){
        if(l<=nl&&nr<=r){Mk(p,k);return;}
        int mid=(nl+nr)>>1;PushDown(p);
        if(l<=mid)Update(nl,mid,l,r,ls(p),k);
        if(r>mid)Update(mid+1,nr,l,r,rs(p),k);
        PushUp(p);
    }

    int Query(int nl,int nr,int l,int r,int p){
        if(l<=nl&&nr<=r)return tr[p];
        int mid=(nl+nr)>>1,res=0;PushDown(p);
        if(l<=mid)res|=Query(nl,mid,l,r,ls(p));
        if(r>mid)res|=Query(mid+1,nr,l,r,rs(p));
        PushUp(p);return res;
    }

    void GetLR(){
        static int pos[N];
        for(int i=1;i<=n;i++)pos[i]=n+1;
        for(int i=n;i>=1;i--){
            R[i]=pos[col[i]];
            for(int j:w[i]) pos[j]=i;
        }
        for(int i=1;i<=n;i++) pos[i]=0;
        for(int i=1;i<=n;i++){
            L[i]=pos[col[i-1]];
            for(int j:w[i]) pos[j]=i;
        }
    }

    void Solve(){
        for(int i=1;i<=n;i++)
            qr[i].clear();
        GetLR();Build(0,n,1);
        for(int i=1;i<=m;i++){
            int x=X[i],y=Y[i];
            if(x<y) qr[x].emplace_back(y,i);
        }
        Update(0,n,1,n,1,0);
        for(int i=1;i<=n;i++){
            for(auto [j,id]:qr[i]) ans[id]=Query(0,n,i+1,j,1);
            if(i<R[i]) Update(0,n,i+1,R[i],1,i);
        }
    }

    void Main(){
        n=rd;
        for(int i=1;i<n;i++) col[i]=rd;
        for(int i=1;i<=n;i++){
            int k=rd;
            while(k--)w[i].push_back(rd);
        }
        m=rd;
        for(int i=1;i<=m;i++)
            X[i]=rd,Y[i]=rd;
        Solve();
        for(int i=1;i<=m;i++)X[i]=n-X[i]+1,Y[i]=n-Y[i]+1;
        reverse(col+1,col+n);
        for(int i=1;i<=n/2;i++)
            swap(w[i],w[n-i+1]);
        Solve();
        for(int i=1;i<=m;i++)
            printf("%s\n",ans[i]?"NO":"YES");
    }
}

signed main(){
    Smilemask::Main();
    return 0;
}
/*
start thinking:

finish thinking:
*/