比赛 20160909 评测结果 AAAEAAE
题目名称 基本的图问题 最终得分 71
用户昵称 ミント 运行时间 0.954 s
代码语言 C++ 内存使用 11.08 MiB
提交时间 2016-09-09 21:02:57
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

#include <vector>

using namespace std;

const int maxn = 50000 + 100;
int st[maxn][32][2];
int num[maxn], n;
int ufs[maxn];
 
void Init(){
	memset(st, 0, sizeof(st));
	memset(num, 0, sizeof(num));
	for(int i=0;i<maxn;i++)ufs[i] = i;
	return ;
}
void make(int flag){
	for(int i=1;i<=n;i++)
		st[i][0][flag] = num[i];
	for(int i=1;(1<<i)<=n;i++)
		for(int j=1;j+(1<<i)-1<=n;j++){
			if(!flag)st[j][i][flag] = max(st[j][i-1][flag], st[j+(1<<(i-1))][i-1][flag]);
			else st[j][i][flag] = min(st[j][i-1][flag], st[j+(1<<(i-1))][i-1][flag]);
		}
	return ;
}
inline int q(int l, int r, int flag){
	int k = 0;
	while((1<<(k+1))<=r-l+1)k++;
	if(!flag)return max(st[l][k][flag], st[r-(1<<k)+1][k][flag]);
	else return min(st[l][k][flag], st[r-(1<<k)+1][k][flag]);
}
inline int find(int x){
	if(ufs[x]!=x)return ufs[x] = find(ufs[x]);
	return ufs[x];
}
inline void merge(int x, int y){
	ufs[find(x)] = find(y);
	return ;
}
int main(){
	freopen("basicgraph.in", "r", stdin);
	freopen("basicgraph.out", "w", stdout);
	
	Init();
	
	cin>>n;
	for(int i=1;i<=n;i++)cin>>num[i];
	make(0);make(1);
	
	int m;cin>>m;
	while(m--){
		int a, b;cin>>a>>b;
		int mx = q(a, b, 0), mn = q(a, b, 1);
		merge(mx, mn);
		//cout<<mx<<' '<<mn<<endl;
	}
	
	int k;cin>>k;
	while(k--){
		int a, b;cin>>a>>b;
		if(find(a)==find(b))cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}