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

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn=100010;
const int INF=0x3f3f3f3f;
const int LOG=20;

int n, m;
vector<int> A;
int fa[maxn];
int d1[maxn][LOG];
int d2[maxn][LOG];
int MIN=INF, MAX=-INF; 

int Find(int x)
{
	return fa[x]==x ? x : fa[x]=Find(fa[x]);
}

void RMQ_init()
{
	for(int j=1; (1<<j)<=n; j++)
		for(int i=0; i+(1<<j)-1<n; i++)
			d1[i][j]=min(d1[i][j-1], d1[i+(1<<(j-1))][j-1]),
		    d2[i][j]=max(d2[i][j-1], d2[i+(1<<(j-1))][j-1]);
}

void RMQ(int L, int R)
{
	int k=0;
	while(1<<(k+1) <= R-L+1) k++;
	MIN=min(d1[L][k], d1[R-(1<<k)+1][k]);
	MAX=max(d2[L][k], d2[R-(1<<k)+1][k]);
	return;
}

int Qin()
{
	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 init()
{
	n=Qin();
	for(int i=1; i<=n; i++) fa[i]=i;
	for(int i=0; i<n; i++) d1[i][0]=Qin(), d2[i][0]=d1[i][0];
	RMQ_init();
	m=Qin();
	for(int i=1; i<=m; i++) {
		int S=Qin();
		int E=Qin();
		MIN=INF; MAX=-INF;
		RMQ(S-1, E-1);
		int x=Find(MIN);
		int y=Find(MAX);
		fa[x]=y;
	}
	int k=Qin();
	for(int i=1; i<=k; i++) {
		int u=Qin();
		int v=Qin();
		if(Find(u)==Find(v)) printf("YES\n");
		else printf("NO\n");
	}
}

int main()
{
	freopen("basicgraph.in", "r", stdin);
	freopen("basicgraph.out", "w", stdout);
	init();
	return 0;
}