考虑什么样的区间是合法的。

题目很二分图。不妨将 $A$ 看成左部点，$B$ 看成右部点。每次询问的区间 $[l,r]$ 中，对于所有 $i\in[l,r]$，$A_i$ 向所有满足 $j\in[l,i)\cup(i,r],A_i>B_j$ 的 $B_j$ 连边，答案等价于是否有完美匹配。

将 $A$ 与 $B$ 放在一起从小到大排序，若最后排出来的形式为 $\underbrace{BABABBA\dots}_{k个A,k个B}B_xA_x\dots$ 必然无解。每个 $A_i$ 对一个前缀里的所有 $B$ 连边然后删掉边 $(A_i,B_i)$。根据 hall 定理，这 $k$ 个 $A$ 与 $A_x$ 的邻集大小为 $k<k+1$，则不存在完美匹配。

发现好像构造不出来其他的无解形式了，尝试归纳上述情况：存在 $i$ 满足 $B_i,A_i$ 相邻且 $B_i$ 之前的 $A$ 与 $B$ 数量相等。

由于 $B_i<A_i$，则排序之后的形式必然是一个合法的括号匹配，不考虑删边，始终有 $\lvert S\rvert\leq\lvert T\rvert$（$T$ 为 $S$ 的邻集）；删除 $(A_i,B_i)$ 后，有 $\lvert S\rvert\leq\lvert T\rvert-1$，当且仅当在上述情况时取等。

有了结论后，实现是简单的。

将第 $i$ 个学生看成区间 $[B_i,A_i]$，结论等价于存在一个区间与其他区间的交集为空。预处理 $L_i,R_i$ 分别表示 $i$ 左边最近的与 $i$ 有交的区间， $i$ 右边最近的与 $i$ 有交的区间（不存在则分别为极小/极大值），合法要求 $\forall i\in[l,r],[l,r]\notin(L_i,R_i)$。

求 $L_i,R_i$ 是区间覆盖求极值，判合法可以离线扫描线，时间复杂度 $O((N+Q)\log N)$。

Code

#include<bits/stdc++.h>
#define lt id<<1
#define rt id<<1|1
#define fi first
#define se second
#define mk make_pair
#define pi pair<int,int>
using namespace std;
const int N=5e5+10,M=N<<1,K=M<<2;
inline int read()
{
    int x=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x;
}
int n,q,a[N],b[N],L[N],R[N],Mx[K];
bool ans[N];
pi num[K],tag[K];
vector<pi>ask[M];
vector<int>ned[M];
inline void Max(int &x,int y) {x=x>y?x:y;}
void build(int id,int l,int r)
{
    num[id]=mk(0,1e9);
    if(l==r) return;
    int mid=(l+r)>>1;
    build(lt,l,mid);
    build(rt,mid+1,r);
}
void push_up(int id) {num[id]=max(num[lt],num[rt]);}
void push_down(int id)
{
    if(!tag[id].fi) return;
    num[lt]=num[rt]=tag[lt]=tag[rt]=tag[id];
    tag[id].fi=0;
}
void add(int id,int l,int r,int L,int R,int T,int x)
{
    if(l>R||r<L) return;
    if(L<=l&&r<=R)
        return num[id]=tag[id]=mk(T,x),void();
    push_down(id);
    int mid=(l+r)>>1;
    add(lt,l,mid,L,R,T,x);
    add(rt,mid+1,r,L,R,T,x);
    push_up(id);
}
pi query(int id,int l,int r,int L,int R)
{
    if(l>R||r<L) return mk(0,0);
    if(L<=l&&r<=R) return num[id];
    push_down(id);
    int mid=(l+r)>>1;
    return max(query(lt,l,mid,L,R),query(rt,mid+1,r,L,R));
}
void Push_up(int id) {Mx[id]=max(Mx[lt],Mx[rt]);}
void Build(int id,int l,int r)
{
    if(l==r)
        return Mx[id]=R[l],void();
    int mid=(l+r)>>1;
    Build(lt,l,mid);
    Build(rt,mid+1,r);
    Push_up(id);
}
void Del(int id,int l,int r,int x)
{
    if(l==r)
        return Mx[id]=0,void();
    int mid=(l+r)>>1;
    x<=mid?Del(lt,l,mid,x):Del(rt,mid+1,r,x);
    Push_up(id);
}
int Query(int id,int l,int r,int L,int R)
{
    if(l>R||r<L) return 0;
    if(L<=l&&r<=R) return Mx[id];
    int mid=(l+r)>>1;
    return max(Query(lt,l,mid,L,R),Query(rt,mid+1,r,L,R));
}
int main()
{
  freopen("a.in","r",stdin);
  freopen("a.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) b[i]=read();
    for(int i=1;i<=n;i++)
        L[i]=query(1,1,n+n,b[i],a[i]).se,add(1,1,n+n,b[i],a[i],i,i);
    build(1,1,n+n);
    for(int i=n;i;i--)
        R[i]=query(1,1,n+n,b[i],a[i]).se,add(1,1,n+n,b[i],a[i],n-i+1,i);
    for(int i=1;i<=n;i++) ned[L[i]].push_back(i);
    Build(1,1,n);
    q=read();
    for(int i=1,l,r;i<=q;i++)
        l=read(),r=read(),ask[l].push_back(mk(r,i));
    for(int i=n;i;i--)
    {
        for(int x:ned[i]) Del(1,1,n,x);
        for(pi x:ask[i])
            ans[x.se]=Query(1,1,n,i,x.fi)<=x.fi;
    }
    for(int i=1;i<=q;i++) puts(ans[i]?"Yes":"No");
    return 0;
}