比赛 |
防止浮躁的小练习v0.5 |
评测结果 |
AAAAAAA |
题目名称 |
基本的图问题 |
最终得分 |
100 |
用户昵称 |
GROWL GOOD BOYส็ |
运行时间 |
0.687 s |
代码语言 |
C++ |
内存使用 |
3.75 MiB |
提交时间 |
2016-10-15 15:45:24 |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
const int maxn=100000+10;
int N,M,Q;
int ma[maxn<<2],mi[maxn<<2],fa[maxn];
void Build(int rt,int l,int r)
{
if(l==r)
{
scanf("%d",&ma[rt]);
fa[l]=l;
mi[rt]=ma[rt];
//printf("l==%d data==%lld\n",l,A[pos[l]]);
return;
}
int mid=(l+r)>>1;
Build(lson);
Build(rson);
mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);
ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);
}
void change(int rt,int l,int r,int s,int x)
{
if(l==r)
{
mi[rt]=ma[rt]=x;
return;
}
int mid=(l+r)>>1;
if(s<=mid)change(lson,s,x);
else change(rson,s,x);
mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);
ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);
}
int queryma(int rt,int l,int r,int s,int t)
{
if(s<=l&&t>=r)
{
return ma[rt];
}
int mid=(l+r)>>1;
if(t<=mid)return queryma(lson,s,t);
if(s>mid)return queryma(rson,s,t);
return max(queryma(lson,s,t),queryma(rson,s,t));
}
int querymi(int rt,int l,int r,int s,int t)
{
if(s<=l&&t>=r)
{
return mi[rt];
}
int mid=(l+r)>>1;
if(t<=mid)return querymi(lson,s,t);
if(s>mid)return querymi(rson,s,t);
return min(querymi(lson,s,t),querymi(rson,s,t));
}
int find(int x)
{
int fx=x,t;
while(fa[fx]!=fx)
{
fx=fa[fx];
}
while(fa[x]!=fx)
{
t=fa[x],fa[x]=fx,x=t;
}
return fx;
}
int main()
{
freopen("basicgraph.in","r",stdin);
freopen("basicgraph.out","w",stdout);
scanf("%d",&N);
Build(1,1,N);
scanf("%d",&M);
for(int s,t,x,y,rtx,rty,i=1;i<=M;i++)
{
scanf("%d%d",&s,&t);
x=querymi(1,1,N,s,t);
y=queryma(1,1,N,s,t);
rtx=find(x),rty=find(y);
if(fa[rtx]!=rty)fa[rtx]=rty;
}
scanf("%d",&Q);
for(int x,y,rtx,rty,i=1;i<=Q;i++)
{
scanf("%d%d",&x,&y);
rtx=find(x);
rty=find(y);
if(rtx==rty)puts("YES");
else puts("NO");
}
fclose(stdin);
fclose(stdout);
return 0;
}