比赛 20160909 评测结果 WAWWWWW
题目名称 基本的图问题 最终得分 14
用户昵称 KZNS 运行时间 1.198 s
代码语言 C++ 内存使用 14.31 MiB
提交时间 2016-09-09 20:27:04
显示代码纯文本
//KZNS
//Best WiL
#include <cstdio>
#include <algorithm>
using namespace std;
#define Nmax 100003
inline int loog(const int x) {
	int u = 1;
	for (int i = 0; true; i++)
		if (x < (u <<= 1))
			return i;
}
int N;
int A[Nmax];
int mx[Nmax][20];
int mn[Nmax][20];
inline int miin(const int a, const int b) {
	if (A[a] < A[b])
		return a;
	else
		return b;
}
inline int maax(const int a, const int b) {
	if (A[a] > A[b])
		return a;
	else
		return b;
}
int fa[Nmax];
int vv[Nmax] = {0};
int FA(int x) {
	if (fa[x] == x)
		return x;
	return fa[x] = FA(fa[x]);
}
inline void hb(int a, int b) {
	a = FA(a);
	b = FA(b);
	if (a != b) {
		if (vv[a] == vv[b]) {
			fa[a] = b;
			vv[b]++;
		}
		else if (vv[a] < vv[b])
			fa[a] = b;
		else
			fa[b] = a;
	}
}
int main() {
	freopen("basicgraph.in", "r", stdin);
	freopen("basicgraph.out", "w", stdout);
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d", A+i);
		fa[i] = mx[i][0] = mn[i][0] = i;
	}
	for (int k = 1; 1<<k <= N; k++) {
		for (int i = 1; i+(1<<k)-1 <= N; i++) {
			mx[i][k] = maax(mx[i][k-1], mx[i+(1<<k-1)][k-1]);
			mn[i][k] = miin(mn[i][k-1], mn[i+(1<<k-1)][k-1]);
		}
	}
	int m;
	scanf("%d", &m);
	int l, r, c, d, u;
	while (m--) {
		scanf("%d %d", &l, &r);
		u = loog(r-l+1);
		c = maax(mx[l][u], mx[r-(1<<u)+1][u]);
		d = miin(mn[l][u], mn[r-(1<<u)+1][u]);
		hb(c, d);
	}
	scanf("%d", &m);
	while (m--) {
		scanf("%d %d", &l, &r);
		if (FA(l) == FA(r))
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}
//All Illu
//UBWH