比赛 防止浮躁的小练习v0.5 评测结果 AAAAAAA
题目名称 基本的图问题 最终得分 100
用户昵称 _Itachi 运行时间 0.853 s
代码语言 C++ 内存使用 5.25 MiB
提交时间 2016-10-15 15:36:28
显示代码纯文本
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
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 _find(const int& a){
	if(root[a] != a) root[a] = _find(root[a]);
	return root[a];
}
inline void Union(const int& a, const int& b){
	int ra = _find(a), rb = _find(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 _getmin(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 _getmin(l, mid, s, t, lch);
	else if(s >= mid+1) return _getmin(mid+1, r, s, t, rch);
	return min(_getmin(l, mid, s, mid, lch), _getmin(mid+1, r, mid+1, t, rch));
}
int _getmax(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 _getmax(l, mid, s, t, lch);
	else if(s >= mid+1) return _getmax(mid+1, r, s, t, rch);
	return max(_getmax(l, mid, s, mid, lch), _getmax(mid+1, r, mid+1, t, rch));
}
void _work(){
	_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(_getmin(1, n, l, r, 1), _getmax(1, n, l, r, 1));
	}
	_read(k);
	int s, t;
	for(int i = 1; i <= k; i++){
		_read(s); _read(t);
		if(_find(s) == _find(t)) puts("YES");
		else puts("NO");
	}
}
int main(){
#define _Rabit _RABIT
#ifdef _Rabit
	freopen("basicgraph.in","r",stdin);
	freopen("basicgraph.out","w",stdout);
#endif
	_work();
#ifndef _Rabit
	getchar(),getchar();
#endif
	fclose(stdin);fclose(stdout);
}