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

#include <fstream>
#include <iostream>
#include <cmath>

using namespace std;

const int MAX_VALUE = 100001;
int MaxR[MAX_VALUE][18],MinR[MAX_VALUE][18];
int Data[MAX_VALUE];
int FatherOf[MAX_VALUE];

inline void SparseTable()
{
	for (int i = 1;i < MAX_VALUE;++i)
		MaxR[i][0] = MinR[i][0] = Data[i];
	for (int j = 1;j <= 16;++j)
		for (int i = 1;i + (1 << (j - 1)) <= MAX_VALUE;++i)
		{
			MaxR[i][j] = MaxR[i][j - 1] >= MaxR[i + (1 << (j - 1))][j - 1] ? MaxR[i][j - 1] : MaxR[i + (1 << (j - 1))][j - 1];
			MinR[i][j] = MinR[i][j - 1] <= MinR[i + (1 << (j - 1))][j - 1] ? MinR[i][j - 1] : MinR[i + (1 << (j - 1))][j - 1];
		}
}
inline int Max(int left,int right)
{
	int k = int(log2(right - left + 1.0));
	return MaxR[left][k] >= MaxR[right - (1 << k) + 1][k] ? MaxR[left][k] : MaxR[right - (1 << k) + 1][k];
}
inline int Min(int left,int right)
{
	int k = int(log2(right - left + 1.0));
	return MinR[left][k] <= MinR[right - (1 << k) + 1][k] ? MinR[left][k] : MinR[right - (1 << k) + 1][k];
}

inline int GetInt(FILE *fin)
{
	int num = 0, flag = 0;
	char ch;
	ch = fgetc(fin);
	while (' ' == ch || '\n' == ch)
		ch = fgetc(fin);
	if ('-' == ch)
	{
		flag = 1;
		ch = fgetc(fin);
	}
	while ('0' <= ch && ch <= '9')
	{
		num = (num << 3) + (num << 1) + ch - '0';
		ch = fgetc(fin);
	}
	if (flag)
		return -num;
	else
		return num;
}

inline int FindFather(int x)
{
	if (FatherOf[x] != x)
		FatherOf[x] = FindFather(FatherOf[x]);
	return FatherOf[x];
}
inline void Merge(int x, int y)
{
	int fx = FindFather(x), fy = FindFather(y);
	if (fx != fy)
		FatherOf[fy] = fx;
}

int Main()
{
	FILE *fin = fopen("basicgraph.in", "r");
	FILE *fout = fopen("basicgraph.out", "w");

	int DataSize = GetInt(fin);
	Data[1] = GetInt(fin);
	FatherOf[1] = 1;
	Data[0] = 0;
	for (int i = 2; i <= DataSize; ++i)
	{
		Data[i] = GetInt(fin);
		FatherOf[i] = i;
	}

	SparseTable();
	
	int DataSize_L = GetInt(fin);
	int left, right;
	for (int i = 1; i <= DataSize_L; ++i)
	{
		left = GetInt(fin);
		right = GetInt(fin);
		Merge(Max(left,right),Min(left,right));
	}

	int DataSize_Q = GetInt(fin);
	int x, y;
	for (int i = 1; i <= DataSize_Q; ++i)
	{
		x = GetInt(fin);
		y = GetInt(fin);
		if (FindFather(x) == FindFather(y))
			fprintf(fout, "YES\n");
		else
			fprintf(fout, "NO\n");
	}

	fclose(fin);
	fclose(fout);

	return 0;
}
int asd = Main();
int main() { ; }