比赛 20160909 评测结果 AAAAAAA
题目名称 基本的图问题 最终得分 100
用户昵称 AAAAAAAAAA 运行时间 1.294 s
代码语言 C++ 内存使用 26.49 MiB
提交时间 2016-09-09 22:54:58
显示代码纯文本
#include<cstdio>
#include<algorithm>
using namespace std;
int dmax[100001][33]={0};//d[i][j]表示从i开始2^j个数的最大值
int dmin[100001][33]={0};//最小值
int f[100001]={0},d[100001]={0};
inline int qr()
{
	char c;
	c=getchar();
	while(!(c>='0'&&c<='9'))
	{
		c=getchar();
	}
	int p=0;
	while(c>='0'&&c<='9')
	{
		p=(p<<1)+(p<<3)+c-'0';
		c=getchar();
	}
	return p;
}
inline void memset(int n)
{
	int i;
	for(i=1;i<=n;i++)
	{
		f[i]=i;
	}
}
inline int findf(int x)
{
	if(f[x]!=x)
	{
		f[x]=findf(f[x]);
	}
	return f[x];
}
inline void merge(int x,int y)
{
	int xx=findf(x);
	int yy=findf(y);
	if(xx!=yy)
	{
	if(d[xx]>d[yy])
	{
		f[yy]=xx;
	}
	if(d[xx]<d[yy])
	{
		f[xx]=yy;
	}
	if(d[xx]==d[yy])
	{
		f[xx]=yy;
		d[yy]++;
	}
	}
}
inline int LOG(int n)
{
	int x=2,k=0;
	while(x<=n)
	{
		k++;
		x<<=1;
	}
	return k;
}
int main(){
	freopen("basicgraph.in","r",stdin);
	freopen("basicgraph.out","w",stdout);
	int n,x,y,a[100001]={0},i,j,k,m;
	n=qr();
	for(i=1;i<=n;i++)
	{
		a[i]=qr();
	}
	for(i=1;i<=n;i++)
	{
		dmax[i][0]=a[i];
		dmin[i][0]=a[i];
	}
	for(j=1;j<LOG(n)+1;++j)
	{
		for(i=1;i<=n;++i)
		{
			if(i+(1<<j)-1<=n)
			{
			dmax[i][j]=max(dmax[i][j-1],dmax[i+(1<<(j-1))][j-1]);
			dmin[i][j]=min(dmin[i][j-1],dmin[i+(1<<(j-1))][j-1]);
			}
		}
	}
	m=qr();
	memset(n);
	for(i=1;i<=m;i++)
	{
		x=qr();
		y=qr();
		int temp;
		temp=LOG(y-x+1);
		int maxx=max(dmax[x][temp],dmax[y-(1<<temp)+1][temp]);
		int minx=min(dmin[x][temp],dmin[y-(1<<temp)+1][temp]);
		merge(maxx,minx);
	}
	k=qr();
	for(i=1;i<=k;i++)
	{
		x=qr();
		y=qr();
		if(findf(x)==findf(y))
		{
			printf("YES\n");
		}
		else
		{
			printf("NO\n");
		}
	}
	return 0;
}