比赛 20160909 评测结果 AAAAAAA
题目名称 基本的图问题 最终得分 100
用户昵称 Mealy 运行时间 1.927 s
代码语言 C++ 内存使用 68.95 MiB
提交时间 2016-09-09 20:28:57
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
const int nmax=500086;
const int vmax=20;
int n,op,q;
int tmpl,tmpr;
int tmpmax,tmpmin;
int r[nmax];
int unp[nmax];
int arrrmqmin[nmax][vmax];
int arrrmqmax[nmax][vmax];
void PreDowithSetSet()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&r[i]);
		unp[i]=i;
	}
	
}
void PreRMQ()
{
	for(int i=1;i<=n;i++)
	{
		arrrmqmax[i][0]=r[i];
		arrrmqmin[i][0]=r[i];
	}
}

void RMQ()
{
	for(int j=1;j<20;j++)
		for(int i=1;i<=n;i++)
			if(i+(1<<j)-1<=n)
			{
				arrrmqmin[i][j]=min(arrrmqmin[i][j-1],arrrmqmin[i+(1<<(j-1))][j-1]);
				arrrmqmax[i][j]=max(arrrmqmax[i][j-1],arrrmqmax[i+(1<<(j-1))][j-1]);
			}
}
int GetMin(int l,int r)
{
	int k=int(floor(log2(r-l+1)));
	return min(arrrmqmin[l][k],arrrmqmin[r-(1<<k)+1][k]);
}
int GetMax(int l,int r)
{
	int k=int(floor(log2(r-l+1)));
	return max(arrrmqmax[l][k],arrrmqmax[r-(1<<k)+1][k]);
}
int SetFind(int a)
{
	if(a==unp[a])
		return a;
	unp[a]=SetFind(unp[a]);
	return unp[a];
}

void SetMerge(int x,int y)
{
	int px=SetFind(x);
	int py=SetFind(y);
	unp[px]=py;
}

int main()
{
	freopen("basicgraph.in","r",stdin);
	freopen("basicgraph.out","w",stdout);
	PreDowithSetSet();
	PreRMQ();
	RMQ();
	scanf("%d",&op);
	for(int i=1;i<=op;i++)
	{
		scanf("%d%d",&tmpl,&tmpr);
		tmpmin=GetMin(tmpl,tmpr);
		tmpmax=GetMax(tmpl,tmpr);
		SetMerge(tmpmin,tmpmax);
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&tmpl,&tmpr);
		if(SetFind(tmpl)==SetFind(tmpr))
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}