记录编号	307445	评测结果	AAAAAAA
题目名称	基本的图问题	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	1.478 s
提交时间	2016-09-15 12:01:30	内存使用	1.08 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
ll read(){
	ll x=0; long long f=1; char ch;
	while(ch=getchar(), !isdigit(ch)) if(ch=='-') f=-1;
	x = ch-'0';
	while(ch=getchar(),  isdigit(ch)) x = x*10+ch-'0';
	return x*f;
}
const ll maxn = 100005;
int N, M, Q, n[maxn], fa[maxn];
int find(int x){ return fa[x]==x?x:fa[x]=find(fa[x]); }

int mmax(int a, int b){return max(a,b);}
int mmin(int a, int b){return min(a,b);}
struct RMQ{
	int B, Bn, l, r, *nn, len;
	vector <int> b, dl, dr, p;
	vector < vector<int> > d;
	vector <RMQ*> son;

	int (*cmp)(int, int);
	int block(int i){ return (i-1)/B+1;}
	RMQ(int*n, int ll, int rr, int (*x)(int, int)):l(ll), r(rr){
		cmp = x;
		if(ll==rr) return;
		nn = n+l-1;
		len = r-l+1;
		b.resize(len+2), dl.resize(len+2), dr.resize(len+2);
		B = (int)floor(sqrt(len));
		for(int i=1; i<=len; ++i) b[i] = block(i);
		Bn = block(len);
		p.resize(Bn+2);
		for(int i=1; i<=Bn; ++i) p[i] = 1+(i-1)*B; p[Bn+1] = 1+len;
		d.resize(Bn+2);
		for(int i=1; i<=Bn; ++i) d[i].resize(Bn+2);
		for(int i=1; i<=Bn; ++i){
			int minn = nn[p[i]];
			for(int j=p[i]; b[j]==i; ++j) minn = cmp(minn, nn[j]), dl[j] = minn;
			minn = nn[p[i+1]-1];
			for(int j=p[i+1]-1; b[j]==i; --j) minn = cmp(minn, nn[j]), dr[j] = minn;
			d[i][i+1] = dr[p[i]];
		}
		for(int i=Bn-1; i; --i) for(int j=i+2; j<=Bn+1; ++j) 
			d[i][j] = cmp(d[i+1][j], d[i][j-1]);
		son.resize(Bn+1);
		for(int i=1; i<=Bn; ++i) son[i] = new RMQ(n, l+p[i]-1, l+p[i+1]-2, cmp);
	}
	int Query(int s, int t){
		if(s==t) return nn[s];
		if(s>t) return -1;
		int ll = block(s), rr = block(t);
		if(ll==rr) return son[ll]->Query(s-p[ll]+1, t-p[ll]+1);
		if(ll+1==rr) return cmp(dr[s], dl[t]);
		else return cmp(d[ll+1][rr], cmp(dr[s], dl[t]));
	}
}*s1, *s2;
int main(){	
	// int __size__=128<<20;
	// char *__p__=(char*)malloc(__size__)+__size__;
	// __asm__("movl %0, %%esp\n"::"r"(__p__));
	freopen("basicgraph.in","r",stdin); freopen("basicgraph.out","w",stdout);
	N = read(); 
	for(int i=1; i<=N; ++i) n[i] = read(), fa[i] = i;
	s1 = new RMQ(n, 1, N, mmin);
	s2 = new RMQ(n, 1, N, mmax);

	M = read();
	for(int i=1,a,b,x,y,fx,fy; i<=M; ++i){
		a = read(), b = read();

		x = s1->Query(a, b);
		y = s2->Query(a, b);

		fx = find(x), fy = find(y);
		if(fx!=fy) fa[fy] = fx;
	}
	Q = read();
	for(int i=1,a,b,fa,fb; i<=Q; ++i){
		a = read(), b = read();
		fa = find(a), fb = find(b);
		puts(fa==fb ? "YES" : "NO");
	}
	getchar(),getchar();
	return 0;
}
/*
2 3 5 4 1
2 3 4 1 0
2 1 0 0 0
2 3 5 4 1
3 5 5 4 0
5 5 0 0 0
 */