记录编号	304868	评测结果	AAAAAAA
题目名称	基本的图问题	最终得分	100
用户昵称	kxxy	是否通过	通过
代码语言	C++	运行时间	1.577 s
提交时间	2016-09-09 22:10:27	内存使用	101.63 MiB

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int maxn=500010;
const int maxx=30;
int n,m,k;
int l,r;
int Amax,Amin;
int a[maxn];
int f[maxn];
int dmin[maxn][maxx];
int qmax[maxn][maxx];
int read()
{
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9')
		c=getchar();
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}
void RMQ_INIT()
{
	for(int i=1;i<=n;i++)
	{
		dmin[i][0]=a[i];
		qmax[i][0]=a[i];
	}
	for(int j=1;j<20;j++)
		for(int i=1;i<=n;i++)
		{
			if(i+(1<<j)-1<=n)
			{
				dmin[i][j]=min(dmin[i][j-1],dmin[i+(1<<(j-1))][j-1]);
				qmax[i][j]=max(qmax[i][j-1],qmax[i+(1<<(j-1))][j-1]);
			}
		}
}
int minn(int l,int r)
{
	int k=0;
	while(1<<(k+1)<=r-l+1)
		k++;
	return min(dmin[l][k],dmin[r-(1<<k)+1][k]);
}
int maxc(int l,int r)
{
	int k=0;
	while(1<<(k+1)<=r-l+1)
		k++;
	return max(qmax[l][k],qmax[r-(1<<k)+1][k]);
}
int find(int x)
{
	if(x==f[x])
		return x;
	return f[x]=find(f[x]);
}
void merge(int x,int y)
{
	int f1=find(x);
	int f2=find(y);
	f[f1]=f2;
}
int main()
{
	freopen("basicgraph.in","r",stdin);
	freopen("basicgraph.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		f[i]=i;
	}
	RMQ_INIT();
	m=read();
	for(int i=1;i<=m;i++)
	{
		l=read(),r=read();
		Amin=minn(l,r);
		Amax=maxc(l,r);
		merge(Amin,Amax);
	}
	k=read();
	for(int i=1;i<=k;i++)
	{
		l=read(),r=read();
		int f1=find(l);
		int f2=find(r);
		if(f1==f2)
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
	}
	return 0;
}