Submission #31554184

---

Source Code Expand

#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int MN=5e5+5;
const int INF=1e9;
int a[MN],b[MN],n,val[MN],l[MN],r[MN],pos[MN],pre[MN],suf[MN];
bool chk[MN],vis[MN];

signed main(void){

#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
#endif

	n=read();int cnt=0;
  
	//Hash
	for(int i=1;i<=n;i++)a[i]=read(),val[++cnt]=a[i];
	for(int i=1;i<=n;i++)b[i]=read(),val[++cnt]=b[i];
	sort(val+1,val+cnt+1);int len=unique(val+1,val+cnt+1)-val-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(val+1,val+len+1,a[i])-val;
	for(int i=1;i<=n;i++)b[i]=lower_bound(val+1,val+len+1,b[i])-val;
  
	for(int i=1;i<=n;i++)if(!pos[b[i]])pos[b[i]]=i;
	for(int i=1;i<=n;i++)if(!vis[a[i]])vis[a[i]]=1,chk[i]=1;
	
	pre[0]=0;
	for(int i=1;i<=n;i++){
		pre[i]=pre[i-1];
		if(chk[i])pre[i]=max(pre[i],pos[a[i]]==0?n+1:pos[a[i]]);
	}
	suf[n+1]=n+1;
	for(int i=n;i>=1;i--){
		suf[i]=suf[i+1];
		if(chk[i])suf[i]=min(suf[i],pos[a[i]]==0?n+1:pos[a[i]]);
	}

	int mn=n+1;
	for(int i=1;i<=n;i++)if(!vis[b[i]])mn=min(mn,i);

	for(int i=1;i<=n;i++){
		if(!chk[i]){l[i]=l[i-1],r[i]=r[i-1];continue;}
		l[i]=pre[i],r[i]=min(suf[i+1],mn)-1;
	}
	int q=read();
	while(q--){
		int x=read(),y=read();
		puts(l[x]<=y&&y<=r[x]?"Yes":"No");
	}

	return 0;
}

Submission Info

Judge Result