比赛 防止浮躁的小练习v0.5 评测结果 AAWWAWW
题目名称 基本的图问题 最终得分 42
用户昵称 dududu 运行时间 0.620 s
代码语言 C++ 内存使用 8.32 MiB
提交时间 2016-10-15 18:29:07
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

#define KN 100010
#define L(i) i<<1
#define R(i) (i<<1)+1
#define inf 100010
#define KM 500010

int getnum()
{
	int res=0;
	char tmp=getchar();
	while(tmp<'0'||tmp>'9') tmp=getchar();
	while(tmp<='9'&&tmp>='0')
	{
		res=res*10+tmp-'0';
		tmp=getchar();
	}
	return res;
}
inline int min(int a,int b)
{
	return a<b? a:b;
}
inline int max(int a,int b)
{
	return a>b? a:b;
}


struct node
{
	int l,r,mid,min_v,max_v;
	node(){
		l=r=mid=min_v=max_v=0;
	}
};

int N,M,K,XDD;

struct Tree
{
	node data[KN*4];
	void build(int L,int R,int i)
	{ 
		int mid=(L+R)>>1;
		data[i].mid=mid;
		data[i].l=L;
		data[i].r=R;
		data[i].max_v=-1;
		data[i].min_v=inf;
		if(L==R) return;
		build(L,mid,L(i));
		build(mid+1,R,R(i));
	}
	
	void updata(int now,int i)
	{	
	//	printf("%d %d %d %d\n",data[i].l,data[i].r,data[i].mid,i);
		data[i].max_v=max(data[i].max_v,XDD);
		data[i].min_v=min(data[i].min_v,XDD);
		if(data[i].l==data[i].r) return; 
		if(now<=data[i].mid) updata(now,L(i));
		else updata(now,R(i));
	}
	
	int min_query(int l,int r,int i)
	{
		int L=data[i].l,R=data[i].r,mid=data[i].mid;
		if(l==L&&r==R) return data[i].min_v;
		if(r<=mid) return min_query(l,r,L(i));
		else if(l>mid) return min_query(l,r,R(i));
		else return min(min_query(l,mid,L(i)),min_query(mid+1,r,R(i)));
	}
	
	int max_query(int l,int r,int i)
	{
		int L=data[i].l,R=data[i].r,mid=data[i].mid;
		if(l==L&&r==R) return data[i].max_v;
		if(r<=mid) return max_query(l,r,L(i));
		else if(l>mid) return max_query(l,r,R(i));
		else return max(max_query(l,mid,L(i)),max_query(mid+1,r,R(i)));
	}
}T;


int f[KN];
int getfa(int dudu)
{
	return f[dudu]= dudu==f[dudu]? dudu:getfa(f[dudu]);
}

void init()
{
	cin>>N;
	T.build(1,N,1);
	for(int i=1;i<=N;i++) f[i]=i,XDD=getnum(),T.updata(i,1);
	
	cin>>M;
	for(int i=1,l,r;i<=M;i++) 
	{
		l=getnum(),r=getnum();
		f[T.min_query(l,r,1)]=T.max_query(l,r,1);
	}
	
	cin>>K;
	for(int i=1,u,v;i<=K;i++)
	{
		u=getnum(),v=getnum();
		if(getfa(u)==getfa(v)) puts("YES");
		else puts("NO");
	}

}

int main()
{
	freopen("basicgraph.in","r",stdin);
	freopen("basicgraph.out","w",stdout);
	init();
	return 0;
}