比赛 |
防止浮躁的小练习v0.5 |
评测结果 |
AAWWAWW |
题目名称 |
基本的图问题 |
最终得分 |
42 |
用户昵称 |
jmisnal |
运行时间 |
0.658 s |
代码语言 |
C++ |
内存使用 |
16.34 MiB |
提交时间 |
2016-10-15 16:37:33 |
显示代码纯文本
#include <iostream>
#include <cstdio>
using namespace std;
int n,m,Q;
int a[100050],dx[100050][20],dd[100050][20];
void init()
{
for(int i=1;i<=n;i++)
dx[i][0]=dd[i][0]=a[i];
for(int j=1;(1<<j)<=n;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
{
dx[i][j]=min(dx[i][j-1],dx[i+(1<<(j-1))][j-1]);
dd[i][j]=max(dd[i][j-1],dd[i+(1<<(j-1))][j-1]);
// cout<<i<<' '<<i+(1<<j)<<' '<<d[i][j]<<endl;
}
}
}
int rminq(int l,int r)
{
int k=0;
while((1<<(k+1))<=r-l)k++;
return min(dx[l][k],dx[r-(1<<k)+1][k]);
}
int rmaxq(int l,int r)
{
int k=0;
while((1<<(k+1))<=r-l)k++;
// cout<<k<<' '<<d[l][k]<<' '<<d[r-(1<<k)][k];
return max(dd[l][k],dd[r-(1<<k)+1][k]);
}
int fa[100050];
int find(int x)
{
int t=x;
while(fa[t]!=t)
t=fa[t];
return t;
}
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]);
fa[i]=i;
}
init();
// return 0;
scanf("%d",&m);
int l,r,x1,x2;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&l,&r);
x1=rminq(l,r),x2=rmaxq(l,r);
// cout<<x1<<' '<<x2<<endl;
fa[x1]=x2;
}
scanf("%d",&Q);
for(int i=1;i<=Q;i++)
{
scanf("%d%d",&l,&r);
if(find(l)==find(r))
printf("YES\n");
else printf("NO\n");
}
return 0;
}