记录编号	304877	评测结果	AAAAAAA
题目名称	基本的图问题	最终得分	100
用户昵称	AAAAAAAAAA	是否通过	通过
代码语言	C++	运行时间	1.279 s
提交时间	2016-09-09 22:37:00	内存使用	26.51 MiB

#include<fstream>
#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(){
	ifstream fin("basicgraph.in");
	ofstream fout("basicgraph.out");
	int n,x,y,a[100001]={0},i,j,k,m;
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>a[i];
	}
	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]);
			}
		}
	}
	fin>>m;
	memset(n);
	for(i=1;i<=m;i++)
	{
		fin>>x>>y;
		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);
	}
	fin>>k;
	for(i=1;i<=k;i++)
	{
		fin>>x>>y;
		if(findf(x)==findf(y))
		{
			fout<<"YES"<<endl;
		}
		else
		{
			fout<<"NO"<<endl;
		}
	}
	return 0;
}