2455. 基本的图问题

【题目描述】

图论是一门有趣且已应用于诸多领域的科学。当我们在解决一些复杂的问题时，我们常常可以建一个图的模型。利用这些模型，我们可以把问题简化并清楚该我们怎么去做。在图论中有很多有名的问题，像汉密尔顿回路，旅行商问题，邮差问题，等等。噢，上帝。它们对于大部分大学生来说都挺难的。别担心，在这个问题中我们只需要考虑一个小问题：图的连通性（啊哈，它对于你来讲足够简单^_^）

我们用（V,E）来表示图。V是G中所有节点的集合，N=|V|是G中节点的个数。E是G中所有边的集合，一条边可以用一个节点对（a1,a2）来表示，意味着a1和a2之间有一条边相连。

现在的问题是：给出一个图G，请求出任意两个节点是否连通（包括直接或间接）。

【输入格式】

第一行包括一个整数n(1≤n≤100000)，G中节点个数。接下来有n个不同的整数，每行一个Ai（1≤Ai≤n，1≤i≤n）。（我们用整数1到n表示G中节点）

A1(1≤A1≤n)

A2(1≤A2≤n)

............

An(1≤An≤n)

下一行包括一个整数m(1≤m≤500000)，下面有m行，每行为一个建边命令，包括两个整数Si和Ei（1≤Si≤n，1≤Ei≤n，Si<Ei，1≤i≤m）

m

S1 E1 (1≤S1≤n，1≤E1≤n，S1<E1)

S2 E2(1≤S2≤n，1≤E2≤n，S2<E2)

............

Sm Em(1≤Sm≤n，1≤Em≤n，Sm<Em)

对于每一个i（1≤i≤m），从前面输入的N个有序结点序列中的[Si,Ei]范围内（即从输入的第Si个数至第Ei个数中）找到一个最小数Amin=min{As1,As2...Ae1}和一个最大数Amax=max{As1，As2…Ae1),然后在G中的结点Amin和Amax之间连一条边。

接下来一行包括一个整数K (1≤k≤100000)， 下面有k个问题。

k

u1 v1 (1≤u1≤n，1≤v1≤n)

u2 v2 (1≤u2≤n，1≤v2≤n)

............

uk vk(1≤uk≤n，1≤vk≤n)

对于每个i（1≤i≤k），你需要回答ui和vi是否连通（包括直接或间接）。

你可以假设每个节点与它自身都是连通的，任意两个节点之间可能会有多条边相连。

【输出格式】

输出文件有K行，其中在第i行如果ui和vi连通(包括直接或间接)，你需要输出“YES”，否则输出“NO”。

【样例输入】

5
2
3
5
4
1
3
2 3
3 5
1 2
3
3 1
5 1
4 5

【样例输出】

YES
YES
NO

【提示】

对于样例输入，共有5个节点顺序是2 3 5 4 1。有3条边：第一条的构建方式是：从输入的第2～3个结点｛3，5｝中找出最小数3，最大数5，在节点3和节点5间连一条边。同理，对于第二条边，在输入序列的第3～5范围内（即{5,4,1}）中找出最小数1，最大数5，节点1和节点5也是直接有边相连的……

【来源】

在此键入。