比赛 |
20160909 |
评测结果 |
AAAAAAA |
题目名称 |
基本的图问题 |
最终得分 |
100 |
用户昵称 |
iortheir |
运行时间 |
1.197 s |
代码语言 |
C++ |
内存使用 |
80.44 MiB |
提交时间 |
2016-09-09 21:55:43 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=500000+100;
int n;
int m;
int father[maxn];
int A[maxn];
int Amin[maxn][20];
int Amax[maxn][20];
int l;
int r;
int Qmin;
int Qmax;
int k;
inline void rmq()
{
for(int i=1;i<=n;++i)
{
Amin[i][0]=A[i];
Amax[i][0]=A[i];
}
for(int j=1;j<20;++j)
{
for(int i=1;i<=n;++i)
{
if(i+(1<<j)-1<=n)
{
Amin[i][j]=min(Amin[i][j-1],Amin[i+(1<<(j-1))][j-1]);
Amax[i][j]=max(Amax[i][j-1],Amax[i+(1<<(j-1))][j-1]);
}
}
}
}
inline int find(int x)
{
if(father[x]!=x)
{
father[x]=find(father[x]);
}
return(father[x]);
}
inline void unionn(int x,int y)
{
x=find(x);
y=find(y);
father[x]=y;
}
inline int gmin(int l,int r)
{
int mid=int(floor(log2(r-l+1)));
return min(Amin[l][mid],Amin[r-(1<<mid)+1][mid]);
}
inline int gmax(int l,int r)
{
int mid=int(floor(log2(r-l+1)));
return max(Amax[l][mid],Amax[r-(1<<mid)+1][mid]);
}
int main()
{
freopen("basicgraph.in","r",stdin);
freopen("basicgraph.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d",&A[i]);
father[i]=i;
}
rmq();
scanf("%d",&m);
for(int i=1;i<=m;++i)
{
scanf("%d%d",&l,&r);
Qmin=gmin(l,r);
Qmax=gmax(l,r);
unionn(Qmin,Qmax);
}
scanf("%d",&k);
int l1;
int r1;
for(int i=1;i<=k;++i)
{
scanf("%d%d",&l1,&r1);
if(find(l1)==find(r1))
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
return 0;
}