比赛 防止浮躁的小练习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;
}