比赛 防止浮躁的小练习v0.5 评测结果 AAWWAWW
题目名称 基本的图问题 最终得分 42
用户昵称 jmisnal 运行时间 0.658 s
代码语言 C++ 内存使用 16.34 MiB
提交时间 2016-10-15 16:37:33
显示代码纯文本
#include <iostream>
#include <cstdio>
using namespace std;
int n,m,Q;
int a[100050],dx[100050][20],dd[100050][20];
void init()
{
	for(int i=1;i<=n;i++)
		dx[i][0]=dd[i][0]=a[i];
	for(int j=1;(1<<j)<=n;j++)
	{
		for(int i=1;i+(1<<j)-1<=n;i++)
		{
			dx[i][j]=min(dx[i][j-1],dx[i+(1<<(j-1))][j-1]);
			dd[i][j]=max(dd[i][j-1],dd[i+(1<<(j-1))][j-1]);
//			cout<<i<<' '<<i+(1<<j)<<' '<<d[i][j]<<endl;
		}			
	}

}
int rminq(int l,int r)
{
	int k=0;
	while((1<<(k+1))<=r-l)k++;
	return min(dx[l][k],dx[r-(1<<k)+1][k]);
}
int rmaxq(int l,int r)
{
	int k=0;
	while((1<<(k+1))<=r-l)k++;
//	cout<<k<<' '<<d[l][k]<<' '<<d[r-(1<<k)][k];
	return max(dd[l][k],dd[r-(1<<k)+1][k]);
}
int fa[100050];
int find(int x)
{
	int t=x;
	while(fa[t]!=t)
		t=fa[t];
	return t;
}
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]);
		fa[i]=i;
	}		
	init();
//	return 0;
	scanf("%d",&m);
	int l,r,x1,x2;

	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&l,&r);
		x1=rminq(l,r),x2=rmaxq(l,r);
	//	cout<<x1<<' '<<x2<<endl;
		fa[x1]=x2;
	}
	scanf("%d",&Q);
	for(int i=1;i<=Q;i++)
	{
		scanf("%d%d",&l,&r);
		if(find(l)==find(r))
			printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}