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

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
const int nmax=500086;
const int vmax=20;
int n,op,q;
int tmpl,tmpr;
int tmpmax,tmpmin;
int r[nmax];
int unp[nmax];
int arrrmqmin[nmax][vmax];
int arrrmqmax[nmax][vmax];
inline void PreDowithSetSet()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&r[i]);
		unp[i]=i;
	}
	
}
inline void PreRMQ()
{
	for(int i=1;i<=n;i++)
	{
		arrrmqmax[i][0]=r[i];
		arrrmqmin[i][0]=r[i];
	}
}

inline void RMQ()
{
	for(int j=1;j<20;j++)
		for(int i=1;i<=n;i++)
			if(i+(1<<j)-1<=n)
			{
				arrrmqmin[i][j]=min(arrrmqmin[i][j-1],arrrmqmin[i+(1<<(j-1))][j-1]);
				arrrmqmax[i][j]=max(arrrmqmax[i][j-1],arrrmqmax[i+(1<<(j-1))][j-1]);
			}
}
inline int GetMin(int l,int r)
{
	int k=int(floor(log2(r-l+1)));
	return min(arrrmqmin[l][k],arrrmqmin[r-(1<<k)+1][k]);
}
inline int GetMax(int l,int r)
{
	int k=int(floor(log2(r-l+1)));
	return max(arrrmqmax[l][k],arrrmqmax[r-(1<<k)+1][k]);
}
inline int SetFind(int a)
{
	if(a==unp[a])
		return a;
	unp[a]=SetFind(unp[a]);
	return unp[a];
}

inline void SetMerge(int x,int y)
{
	int px=SetFind(x);
	int py=SetFind(y);
	unp[px]=py;
}

int main()
{
	freopen("basicgraph.in","r",stdin);
	freopen("basicgraph.out","w",stdout);
	PreDowithSetSet();
	PreRMQ();
	RMQ();
	scanf("%d",&op);
	for(int i=1;i<=op;i++)
	{
		scanf("%d%d",&tmpl,&tmpr);
		tmpmin=GetMin(tmpl,tmpr);
		tmpmax=GetMax(tmpl,tmpr);
		if(SetFind(tmpmin)!=SetFind(tmpmax))
			SetMerge(tmpmin,tmpmax);
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&tmpl,&tmpr);
		if(SetFind(tmpl)==SetFind(tmpr))
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}