记录编号	393197	评测结果	AAAAAAA
题目名称	基本的图问题	最终得分	100
用户昵称	rvalue	是否通过	通过
代码语言	C++	运行时间	0.243 s
提交时间	2017-04-10 10:14:55	内存使用	91.73 MiB

#include <bits/stdc++.h>
using namespace std;

const int INF=0x7FFFFFFF;
const int MAXN=1000010;
const int LG_MAXN=20;

int v;
int e;
int t;
int UFS[MAXN];
int preLg[MAXN];
int stMax[MAXN][LG_MAXN];
int stMin[MAXN][LG_MAXN];

void Initialize();
void Union(int,int);
void LgPreProcess();
int FindRoot(int);
int FastLg(int);
void FastRead(int&);
void BuildEdge();
void STBuild();
int STGetMax(int,int);
int STGetMin(int,int);

int Main(){
	int a,b;

	Initialize();
	LgPreProcess();
	STBuild();
	BuildEdge();
	FastRead(t);
	for(int i=0;i<t;i++){
		FastRead(a);
		FastRead(b);
		if(FindRoot(a)==FindRoot(b))
			puts("YES");
		else
			puts("NO");
	}
	return 0;
}

void Initialize(){
#ifndef ASC_LOCAL
	freopen("basicgraph.in","r",stdin);
	freopen("basicgraph.out","w",stdout);
#endif
	int tmp;
	FastRead(v);
	for(int i=1;i<=v;i++){
		FastRead(tmp);
		stMax[i][0]=tmp;
		stMin[i][0]=tmp;
		UFS[i]=i;
	}
}

void BuildEdge(){
	int l,r;
	FastRead(e);
	for(int i=0;i<e;i++){
		FastRead(l);
		FastRead(r);
		Union(STGetMax(l,r),STGetMin(l,r));
	}
}

int FindRoot(int root){
	if(UFS[root]==root)
		return root;
	else
		return UFS[root]=FindRoot(UFS[root]);
}

inline void Union(int a,int b){
	int ra=FindRoot(a);
	int rb=FindRoot(b);

	if(ra==rb)
		return;
	else
		UFS[ra]=rb;
}

inline int STGetMax(int l,int r){
	int m=FastLg(r-l+1);

	return max(stMax[l][m],stMax[r-(1<<m)+1][m]);
}

inline int STGetMin(int l,int r){
	int m=FastLg(r-l+1);

	return min(stMin[l][m],stMin[r-(1<<m)+1][m]);
}

void STBuild(){
	int m=FastLg(v);
	int k;

	for(int j=1;j<=m;j++){
		for(int i=1;i<=v;i++){
			k=1<<(j-1);
			stMin[i][j]=stMin[i][j-1];
			stMax[i][j]=stMax[i][j-1];
			if(i+k<=v){
				stMin[i][j]=min(stMin[i][j],stMin[i+k][j-1]);
				stMax[i][j]=max(stMax[i][j],stMax[i+k][j-1]);
			}
		}
	}
}

inline void LgPreProcess(){
	int k,i,j,lg;
	for(k=1,i=1,lg=0;i<=v;k=k<<1,lg++){
		for(j=0;j<k;i++,j++){
			preLg[i]=lg;
		}
	}
}

inline int FastLg(int x){
	return preLg[x];
}

void FastRead(int& target){
	target=0;
	bool inv=false;
	register char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch==EOF)
			return;
		if(ch=='-')
			inv=true;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		target=target*10+ch-'0';
		ch=getchar();
	}
	if(inv)
		target=-target;
}

int WORKING=Main();
int main(){;}