比赛 测试 评测结果 AAAAAAA
题目名称 基本的图问题 最终得分 100
用户昵称 YGOI_真神名曰驴蛋蛋 运行时间 0.404 s
代码语言 C++ 内存使用 3.34 MiB
提交时间 2017-04-11 20:36:57
显示代码纯文本
#include <cstdio>
const int MAXN=100010;
const int INF=~0U>>1;
int t[MAXN];
int log2016(int n){int i=0;while(n>>i)i++;return i;}
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a<b?b:a;}
struct FS{
	int f[MAXN];
	void prepare(int N){for(int i=0;i<=N;++i)f[i]=i;}
	int FIND(int i){while(i!=f[i])i=f[i]=f[f[i]];return i;}
	void UNION(int a,int b){a=FIND(a);b=FIND(b);if(a!=b)f[a]=b;}
}s;
struct SET{
	int L;
	int w[MAXN*3+10];
	int (*func)(int,int);
	SET(int (*cmp)(int,int)){func=cmp;}
	void build(int n,int*f){
		L=1<<log2016(n+1);
		for(int i=L+1;i<=L+n;++i)w[i]=f[i-L];
		for(int i=L-1;i>=1;--i)w[i]=func(w[i<<1],w[i<<1|1]);
	}
	int query(int l,int r){
		int p=-func(INF,-INF);
		for(l+=L-1,r+=L+1;l^r^1;l>>=1,r>>=1){
			if(~l&1)p=func(p,w[l^1]);
			if( r&1)p=func(p,w[r^1]);
		}return p;
	}
}minn(min),maxn(max);
int main(){
	freopen("basicgraph.in","r",stdin);
	freopen("basicgraph.out","w",stdout);
	int N;scanf("%d",&N);
	s.prepare(N);
	for(int i=1;i<=N;++i)scanf("%d",&t[i]);
	minn.build(N,t);
	maxn.build(N,t);
	int M;scanf("%d",&M);
	for(int x,y,i=1;i<=M;++i){
		scanf("%d%d",&x,&y);
		s.UNION(minn.query(x,y),maxn.query(x,y));
	}int K;scanf("%d",&K);
	for(int x,y,i=1;i<=K;++i){
		scanf("%d%d",&x,&y);
		puts(s.FIND(x)==s.FIND(y)?"YES":"NO");
	}
	return 0;
}