比赛 |
测试 |
评测结果 |
AAWWAWW |
题目名称 |
基本的图问题 |
最终得分 |
42 |
用户昵称 |
FFF团 |
运行时间 |
0.392 s |
代码语言 |
C++ |
内存使用 |
15.95 MiB |
提交时间 |
2017-04-11 20:35:29 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int Max_num,Min_num;
int A[100001][20];
int B[100001][20];
int fa[100001];
int n,m,k,l,r,x,y;
void Query(int L,int R){
int k=0;
while((1<<(k+1))<=R-L+1) k++;
Max_num=max(B[L][k],B[R-(1<<k)+1][k]);
Min_num=min(A[L][k],A[R-(1<<k)+1][k]);
}
void init(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&A[i][0]);
fa[A[i][0]]=A[i][0];
}
memcpy(B,A,sizeof(A));
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<j)-1<=n;i++){
A[i][j]=min(A[i+(1<<(j-1))][j-1],A[i][j-1]);
B[i][j]=max(B[i+(1<<(j-1))][j-1],B[i][j-1]);
}
}
int find(int x)
{
if(fa[x]==x) return x;
fa[x]=find(fa[x]);
return fa[x];
}
void work(){
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&l,&r);
Query(l,r);
int x1=find(Max_num);
int y1=find(Min_num);
if(x1!=y1) fa[x1]=y1;
}
scanf("%d",&k);
for(int i=1;i<=k;i++){
scanf("%d%d",&x,&y);
int a1=find(x);
int b1=find(y);
if(a1==b1)printf("YES\n");
else printf("NO\n");
}
}
int main(){
freopen("basicgraph.in","r",stdin);
freopen("basicgraph.out","w",stdout);
init();
work();
fclose(stdin);
fclose(stdout);
return 0;
}