比赛 |
测试 |
评测结果 |
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;
}