比赛 测试 评测结果 AAWWAWW
题目名称 基本的图问题 最终得分 42
用户昵称 FFF团 运行时间 0.392 s
代码语言 C++ 内存使用 15.95 MiB
提交时间 2017-04-11 20:35:29
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int Max_num,Min_num;
int A[100001][20];
int B[100001][20];
int fa[100001];
int n,m,k,l,r,x,y;


void Query(int L,int R){
	int k=0;
	while((1<<(k+1))<=R-L+1) k++;
	Max_num=max(B[L][k],B[R-(1<<k)+1][k]);
	Min_num=min(A[L][k],A[R-(1<<k)+1][k]);
	}
void init(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d",&A[i][0]);
		fa[A[i][0]]=A[i][0];
	}
	memcpy(B,A,sizeof(A));
    for(int j=1;(1<<j)<=n;j++)
	for(int i=1;i+(1<<j)-1<=n;i++){
		A[i][j]=min(A[i+(1<<(j-1))][j-1],A[i][j-1]);
		B[i][j]=max(B[i+(1<<(j-1))][j-1],B[i][j-1]);
	}
}
int find(int x)
{
	if(fa[x]==x) return x;
	fa[x]=find(fa[x]);
	return fa[x]; 
}
void work(){
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&l,&r);
		Query(l,r);
		int x1=find(Max_num);
		int y1=find(Min_num);
		if(x1!=y1) fa[x1]=y1;
	}
	scanf("%d",&k);
	for(int i=1;i<=k;i++){
		scanf("%d%d",&x,&y);
		int a1=find(x);
		int b1=find(y);
		if(a1==b1)printf("YES\n");
		else printf("NO\n");
	}
}
int main(){
	freopen("basicgraph.in","r",stdin);
	freopen("basicgraph.out","w",stdout);
	init();
	work();
	fclose(stdin);
	fclose(stdout);
	return 0;
}