比赛 |
防止浮躁的小练习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;
}