比赛 |
20160909 |
评测结果 |
AAAAAAA |
题目名称 |
基本的图问题 |
最终得分 |
100 |
用户昵称 |
AAAAAAAAAA |
运行时间 |
1.294 s |
代码语言 |
C++ |
内存使用 |
26.49 MiB |
提交时间 |
2016-09-09 22:54:58 |
显示代码纯文本
#include<cstdio>
#include<algorithm>
using namespace std;
int dmax[100001][33]={0};//d[i][j]表示从i开始2^j个数的最大值
int dmin[100001][33]={0};//最小值
int f[100001]={0},d[100001]={0};
inline int qr()
{
char c;
c=getchar();
while(!(c>='0'&&c<='9'))
{
c=getchar();
}
int p=0;
while(c>='0'&&c<='9')
{
p=(p<<1)+(p<<3)+c-'0';
c=getchar();
}
return p;
}
inline void memset(int n)
{
int i;
for(i=1;i<=n;i++)
{
f[i]=i;
}
}
inline int findf(int x)
{
if(f[x]!=x)
{
f[x]=findf(f[x]);
}
return f[x];
}
inline void merge(int x,int y)
{
int xx=findf(x);
int yy=findf(y);
if(xx!=yy)
{
if(d[xx]>d[yy])
{
f[yy]=xx;
}
if(d[xx]<d[yy])
{
f[xx]=yy;
}
if(d[xx]==d[yy])
{
f[xx]=yy;
d[yy]++;
}
}
}
inline int LOG(int n)
{
int x=2,k=0;
while(x<=n)
{
k++;
x<<=1;
}
return k;
}
int main(){
freopen("basicgraph.in","r",stdin);
freopen("basicgraph.out","w",stdout);
int n,x,y,a[100001]={0},i,j,k,m;
n=qr();
for(i=1;i<=n;i++)
{
a[i]=qr();
}
for(i=1;i<=n;i++)
{
dmax[i][0]=a[i];
dmin[i][0]=a[i];
}
for(j=1;j<LOG(n)+1;++j)
{
for(i=1;i<=n;++i)
{
if(i+(1<<j)-1<=n)
{
dmax[i][j]=max(dmax[i][j-1],dmax[i+(1<<(j-1))][j-1]);
dmin[i][j]=min(dmin[i][j-1],dmin[i+(1<<(j-1))][j-1]);
}
}
}
m=qr();
memset(n);
for(i=1;i<=m;i++)
{
x=qr();
y=qr();
int temp;
temp=LOG(y-x+1);
int maxx=max(dmax[x][temp],dmax[y-(1<<temp)+1][temp]);
int minx=min(dmin[x][temp],dmin[y-(1<<temp)+1][temp]);
merge(maxx,minx);
}
k=qr();
for(i=1;i<=k;i++)
{
x=qr();
y=qr();
if(findf(x)==findf(y))
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
}