记录编号	305231	评测结果	AAAAAAA
题目名称	基本的图问题	最终得分	100
用户昵称	洛克索耶夫	是否通过	通过
代码语言	C++	运行时间	1.636 s
提交时间	2016-09-10 17:46:27	内存使用	3.77 MiB

#include "cstdio"
#include "cstring"
#include "iostream"
using namespace std;

int n, m, k;
int root[100100];
int tree[400100], minn[400100], maxn[400100];

template <class T> inline void Read(T& a)
{
	a = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch >= '0' && ch <= '9'){
		a = a * 10 + ch - '0';
		ch = getchar();
	}
}

int FindRoot(const int& a)
{
	if(root[a] != a) root[a] = FindRoot(root[a]);
	return root[a];
}

inline void Union(const int& a, const int& b)
{
	int ra = FindRoot(a), rb = FindRoot(b);
	root[ra] = rb;
}

void Build(const int& l, const int& r, const int& rt)
{
	if(l == r){
		Read(tree[rt]);
		maxn[rt] = minn[rt] = tree[rt];
		return;
	}
	const int mid = (l + r) >> 1, lch = rt << 1, rch = (rt << 1) | 1;
	Build(l, mid, lch);
	Build(mid+1, r, rch);
	tree[rt] = tree[lch] + tree[rch];
	minn[rt] = min(minn[lch], minn[rch]);
	maxn[rt] = max(maxn[lch], maxn[rch]);
}

int QueryMin(const int& l, const int& r, const int& s, const int& t, const int& rt)
{
	if(l >= s && r <= t) return minn[rt];
	const int mid = (l + r) >> 1, lch = rt << 1, rch = (rt << 1) | 1;
	if(t <= mid) return QueryMin(l, mid, s, t, lch);
	else if(s >= mid+1) return QueryMin(mid+1, r, s, t, rch);
	//else if(s <= mid && t >= mid+1) 
	return min(QueryMin(l, mid, s, mid, lch), QueryMin(mid+1, r, mid+1, t, rch));
}

int QueryMax(const int& l, const int& r, const int& s, const int& t, const int& rt)
{
	if(l >= s && r <= t) return maxn[rt];
	const int mid = (l + r) >> 1, lch = rt << 1, rch = (rt << 1) | 1;
	if(t <= mid) return QueryMax(l, mid, s, t, lch);
	else if(s >= mid+1) return QueryMax(mid+1, r, s, t, rch);
	return max(QueryMax(l, mid, s, mid, lch), QueryMax(mid+1, r, mid+1, t, rch));
}


int main()
{
	freopen("basicgraph.in", "r", stdin); freopen("basicgraph.out", "w", stdout);
	Read(n);
	for(int i = 1; i <= n; i++) root[i] = i;
	memset(minn, 0x7f, sizeof(minn));
	
	Build(1, n, 1);
	Read(m);
	int l, r;
	for(int i = 1; i <= m; i++){
		Read(l); Read(r);
		Union(QueryMin(1, n, l, r, 1), QueryMax(1, n, l, r, 1));
	}
	
	Read(k);
	int s, t;
	for(int i = 1; i <= k; i++){
		Read(s); Read(t);
		if(FindRoot(s) == FindRoot(t)) puts("YES");
		else puts("NO");
	}
	getchar(); getchar();
	fclose(stdin); fclose(stdout);
	return 0;
}