比赛 20160909 评测结果 AAAAAAA
题目名称 基本的图问题 最终得分 100
用户昵称 iortheir 运行时间 1.197 s
代码语言 C++ 内存使用 80.44 MiB
提交时间 2016-09-09 21:55:43
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>

using namespace std;

const int maxn=500000+100;

int n;
int m;
int father[maxn];
int A[maxn];
int Amin[maxn][20];
int Amax[maxn][20];
int l;
int r;
int Qmin;
int Qmax;
int k;

inline void rmq()
{
	for(int i=1;i<=n;++i)
	{
		Amin[i][0]=A[i];
		Amax[i][0]=A[i];
	}
	for(int j=1;j<20;++j)
	{
		for(int i=1;i<=n;++i)
		{
			if(i+(1<<j)-1<=n)
			{
				Amin[i][j]=min(Amin[i][j-1],Amin[i+(1<<(j-1))][j-1]);
				Amax[i][j]=max(Amax[i][j-1],Amax[i+(1<<(j-1))][j-1]);
			}
		}
	}
}

inline int find(int x)
{
	if(father[x]!=x)
	{
		father[x]=find(father[x]);
	}
	return(father[x]);
}

inline void unionn(int x,int y)
{
	x=find(x);
	y=find(y);
	father[x]=y;
}

inline int gmin(int l,int r)
{
	int mid=int(floor(log2(r-l+1)));
	return min(Amin[l][mid],Amin[r-(1<<mid)+1][mid]);
}

inline int gmax(int l,int r)
{
	int mid=int(floor(log2(r-l+1)));
	return max(Amax[l][mid],Amax[r-(1<<mid)+1][mid]);
}

int main()
{
	freopen("basicgraph.in","r",stdin);
	freopen("basicgraph.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&A[i]);
		father[i]=i;
	}
	rmq();
	scanf("%d",&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&l,&r);
		Qmin=gmin(l,r);
		Qmax=gmax(l,r);
		unionn(Qmin,Qmax);
	}
	scanf("%d",&k);
	int l1;
	int r1;
	for(int i=1;i<=k;++i)
	{
		scanf("%d%d",&l1,&r1);
		if(find(l1)==find(r1))
		{
			cout<<"YES"<<endl;
		}
		else
		{
			cout<<"NO"<<endl;
		}
	}	
	return 0;
}