记录编号	305237	评测结果	AAAAAAA
题目名称	基本的图问题	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	1.277 s
提交时间	2016-09-10 17:53:16	内存使用	23.14 MiB

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <list>
#include <deque>
#include <string>
using namespace std;
#define MAXN 500002
int uset[MAXN];
int finds(int x)
{
    return x == uset[x]?x:uset[x] = finds(uset[x]);
}
int data[MAXN];
struct node
{
    int l, r;
    int ls, rs;
    int maxv;
    int minv;
}ns[MAXN<<1];
int root = 1;
int last = root;
void pushup(int c)
{
    if(c)
    {
        node &d = ns[c];
        d.maxv = max(ns[d.ls].maxv, ns[d.rs].maxv);
        d.minv = min(ns[d.ls].minv, ns[d.rs].minv);
    }
}
int build(int l, int r)
{
    int cur = last++;
    node &d = ns[cur];
    d.l = l;
    d.r = r;
    int m = (l+r)>>1;
    if(l == r)
    {
        d.maxv = data[l];
        d.minv = data[l];
        return cur;
    }
    
    if(l <= m)
    {
        d.ls = build(l, m);
        d.rs = build(m+1, r);
        pushup(cur);
        return cur;
    }else
        return 0;
}
int rmax, rmin;
void querytree(int c, int l, int r)
{
    if(!c)return;
    node &d = ns[c];
    if(d.l == l && r == d.r)
    {
        rmax = max(rmax, d.maxv);
        rmin = min(rmin, d.minv);
        return;
    }
    else if(l >= ns[d.rs].l)querytree(d.rs, l, r);
    else if(r <= ns[d.ls].r)querytree(d.ls, l, r);
    else {querytree(d.ls, l, ns[d.ls].r);querytree(d.rs, ns[d.rs].l, r);}
}

int main()
{
    freopen("basicgraph.in", "r", stdin);
    freopen("basicgraph.out", "w", stdout);
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", data+i);
    build(1, n);
    
    int m;
    scanf("%d", &m);
    for(int i = 1; i <= n; i++)
        uset[i] = i;
    for(int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        rmin = 0x7ffffff3;
        rmax = -0x67346312;
        querytree(root, a, b);
        a = rmax;
        b = rmin;
        
        int x = finds(a);
        int y = finds(b);
        if(x != y)
        {
            uset[x] = y;
        }
    }
    scanf("%d", &m);
    for(int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        if(finds(a) == finds(b))
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}