记录编号	323630	评测结果	AAAAAAA
题目名称	基本的图问题	最终得分	100
用户昵称	jmisnal	是否通过	通过
代码语言	C++	运行时间	0.557 s
提交时间	2016-10-16 21:12:37	内存使用	22.07 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int read()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x;
}
int n,m,Q;
int a[100050],mx[100050][25],mn[100050][25];
int bin[20],L[500000];
void init()
{
	for(int i=1;i<=n;i++)
		mn[i][0]=mx[i][0]=a[i];
//	int m=log(n)/log(2);
	for(int i=1;i<=18;i++)
		for(int j=1;j<=n;j++)
		{
			mx[j][i]=mx[j][i-1];
			mn[j][i]=mn[j][i-1];
			if(j+bin[i]-1<=n)
			{
				mx[j][i]=max(mx[j][i-1],mx[j+bin[i-1]][i-1]);
				mn[j][i]=min(mn[j][i-1],mn[j+bin[i-1]][i-1]);
			}
			else break;
		}			
	

}
int rminq(int l,int r)
{
	int m=L[r-l+1],R=r-bin[m]+1;
	return min(mn[l][m],mn[R][m]);
}
int rmaxq(int l,int r)
{
	int m=L[r-l+1],R=r-bin[m]+1;
	return max(mx[l][m],mx[R][m]);
}
int fa[100050];
int find(int x)
{
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main()
{
	bin[0]=1;
	for(int i=1;i<=19;i++)
		bin[i]=(bin[i-1]<<1);
	L[0]=-1;
	for(int i=1;i<500000;i++)L[i]=L[i>>1]+1;
	freopen("basicgraph.in","r",stdin);
	freopen("basicgraph.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)
		a[i]=read();		
	init();
//	cout<<'a';return 0;
	for(int i=1;i<=n;i++)
		fa[i]=i;
	scanf("%d",&m);
	int l,r,x1,x2,a,b;
	for(int i=1;i<=m;i++)
	{
		//scanf("%d%d",&l,&r);
		l=read(),r=read();
		int m=L[r-l+1],R=r-bin[m]+1;
		if(mx[l][m]>mx[R][m])
			x2=mx[l][m];
		else x2=mx[R][m];
		if(mn[l][m]<mn[R][m])
			x1=mn[l][m];
		else x1=mn[R][m];
	//	x1=rminq(l,r),x2=rmaxq(l,r);
		a=find(x1);b=find(x2);
		if(a!=b)
			fa[a]=b;
		//fa[find(x1)]=find(x2);
	}
//	return 0;
	scanf("%d",&Q);
	for(int i=1;i<=Q;i++)
	{
		scanf("%d%d",&l,&r);
		if(find(l)==find(r))
			printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}