比赛 |
20160909 |
评测结果 |
AAAAAAA |
题目名称 |
基本的图问题 |
最终得分 |
100 |
用户昵称 |
kxxy |
运行时间 |
1.728 s |
代码语言 |
C++ |
内存使用 |
42.22 MiB |
提交时间 |
2016-09-09 21:31:04 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int maxn=500010;
const int maxx=30;
int n,m,k;
int l,r;
int Amax,Amin;
int a[maxn];
int f[maxn];
int dmin[maxn][maxx];
int qmax[maxn][maxx];
int read()
{
int x=0;
char c=getchar();
while(c<'0'||c>'9')
c=getchar();
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return x;
}
void RMQ_INIT()
{
for(int i=1;i<=n;i++)
{
dmin[i][0]=a[i];
qmax[i][0]=a[i];
}
for(int j=1;j<20;j++)
for(int i=1;i<=n;i++)
{
if(i+(1<<j)-1<=n)
{
dmin[i][j]=min(dmin[i][j-1],dmin[i+(1<<(j-1))][j-1]);
qmax[i][j]=max(qmax[i][j-1],qmax[i+(1<<(j-1))][j-1]);
}
}
}
int minn(int l,int r)
{
int k=0;
while(1<<(k+1)<=r-l+1)
k++;
return min(dmin[l][k],dmin[r-(1<<k)+1][k]);
}
int maxc(int l,int r)
{
int k=0;
while(1<<(k+1)<=r-l+1)
k++;
return max(qmax[l][k],qmax[r-(1<<k)+1][k]);
}
int find(int x)
{
if(x==f[x])
return x;
return f[x]=find(f[x]);
}
void merge(int x,int y)
{
int f1=find(x);
int f2=find(y);
f[f1]=f2;
}
int main()
{
freopen("basicgraph.in","r",stdin);
freopen("basicgraph.out","w",stdout);
n=read();
for(int i=1;i<=n;i++)
{
cin>>a[i];
f[i]=i;
}
RMQ_INIT();
m=read();
for(int i=1;i<=m;i++)
{
l=read(),r=read();
Amin=minn(l,r);
Amax=maxc(l,r);
merge(Amin,Amax);
}
k=read();
for(int i=1;i<=k;i++)
{
l=read(),r=read();
int f1=find(l);
int f2=find(r);
if(f1==f2)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}