比赛 防止浮躁的小练习v0.5 评测结果 WAWWWWW
题目名称 基本的图问题 最终得分 14
用户昵称 cdcq 运行时间 0.893 s
代码语言 C++ 内存使用 30.95 MiB
提交时间 2016-10-15 21:41:56
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int read(){int z=0,mark=1;  char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')mark=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0';  ch=getchar();}
	return z*mark;
}
struct ddd{int next,y;}e[1100000];int LINK[110000],ltop=0;
inline void insert(int x,int y){e[++ltop].next=LINK[x];LINK[x]=ltop;e[ltop].y=y;}
int n,m,t,a[110000];
struct dcd{int sleft,sright,mid,smin,smax;}tree[1100000];
void get_SegmentTree(int x,int _left,int _right){
	tree[x].sleft=_left,tree[x].sright=_right,tree[x].mid=(_left+_right)>>1;
	if(_left==_right)  tree[x].smin=tree[x].smax=a[_left];
	else{
		get_SegmentTree(x<<1,_left,tree[x].mid),get_SegmentTree(x<<1|1,tree[x].mid+1,_right);
		tree[x].smin=min(tree[x<<1].smin,tree[x<<1|1].smin);
		tree[x].smax=max(tree[x<<1].smax,tree[x<<1|1].smax);
	}
}
int search_min(int x,int _left,int _right){
	if(tree[x].sleft==_left && tree[x].sright==_right)  return tree[x].smin;
	else if(_left<=tree[x].mid && _right>tree[x].mid)
		return min(search_min(x<<1,_left,tree[x].mid),search_min(x<<1|1,tree[x].mid+1,_right));
	else if(_right<=tree[x].mid)  return search_min(x<<1,_left,_right);
	else  return search_min(x<<1|1,_left,_right);
}
int search_max(int x,int _left,int _right){
	if(tree[x].sleft==_left && tree[x].sright==_right)  return tree[x].smax;
	else if(_left<=tree[x].mid && _right>tree[x].mid)
		return max(search_max(x<<1,_left,tree[x].mid),search_max(x<<1|1,tree[x].mid+1,_right));
	else if(_right<=tree[x].mid)  return search_max(x<<1,_left,_right);
	else  return search_max(x<<1|1,_left,_right);
}
int color[110000],color_cnt=0;
void get_color(int x){
	color[x]=color_cnt;
	for(int i=LINK[x];i;i=e[i].next)if(!color[e[i].y])  get_color(e[i].y);
}
int main(){
	//freopen("ddd.in","r",stdin);
	freopen("basicgraph.in","r",stdin);
	freopen("basicgraph.out","w",stdout);
	memset(color,0,sizeof(color));
	cin>>n;
	for(int i=1;i<=n;i++)  a[i]=read();
	get_SegmentTree(1,1,n);
	int _left,_right;
	cin>>m;
	while(m --> 0){//趋向于
		_left=read(),_right=read();
		int _min=search_min(1,_left,_right),_max=search_max(1,_left,_right);
		insert(_left,_right),insert(_right,_left);
	}
	for(int i=1;i<=n;i++)if(!color[i])  color_cnt++,get_color(i);
	cin>>t;
	while(t --> 0){//趋向于
		_left=read(),_right=read();
		if(color[_left]==color[_right])  printf("YES\n");
		else  printf("NO\n");
	}
	return 0;
}