记录编号	458482	评测结果	AAAAAAA
题目名称	基本的图问题	最终得分	100
用户昵称	Regnig Etalsnart	是否通过	通过
代码语言	C++	运行时间	0.796 s
提交时间	2017-10-11 14:43:09	内存使用	2.34 MiB

#include<cstdio>
using namespace std;
const int maxn=100010,INF=1000000000;
int n,m,k,a[maxn],fa[maxn],minv[maxn<<2],maxv[maxn<<2],ql,qr,i;
int min(int x,int y){return x<y?x:y;}
int max(int x,int y){return x>y?x:y;}
int find(int x)
{
	return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
}
void build(int now,int l,int r)
{
    if(l==r)
    {
    	minv[now]=a[l];
    	maxv[now]=a[l];
    	return;
	}
	int mid=l+((r-l)>>1);
	build(now<<1,l,mid);
	build(now<<1|1,mid+1,r);
	minv[now]=min(minv[now<<1],minv[now<<1|1]);
	maxv[now]=max(maxv[now<<1],maxv[now<<1|1]);
	return;
}
int query1(int now,int l,int r)
{
	if(l>r||ql>r||qr<l)return 0;
	if(l>=ql&&r<=qr)return minv[now];
	int mid=l+((r-l)>>1),ans=INF;
	if(mid>=ql)ans=min(ans,query1(now<<1,l,mid));
    if(mid<qr)ans=min(ans,query1(now<<1|1,mid+1,r));
    return ans;
}
int query2(int now,int l,int r)
{
	if(l>r||ql>r||qr<l)return 0;
	if(l>=ql&&r<=qr)return maxv[now];
	int mid=l+((r-l)>>1),ans=-INF;
	if(mid>=ql)ans=max(ans,query2(now<<1,l,mid));
    if(mid<qr)ans=max(ans,query2(now<<1|1,mid+1,r));
    return ans;
}
int Main()
{
	freopen("basicgraph.in","r",stdin);freopen("basicgraph.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		fa[i]=i;
	}
	build(1,1,n);
	scanf("%d",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&ql,&qr);
		int minn=query1(1,1,n),maxx=query2(1,1,n);
		int r1=find(minn),r2=find(maxx);
		if(r1!=r2)fa[r1]=r2;
	}
	scanf("%d",&k);
	for(i=1;i<=k;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		if(find(u)==find(v))printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}
int main(){;};
int syy=Main();