比赛 防止浮躁的小练习v0.5 评测结果 AAATAAT
题目名称 基本的图问题 最终得分 71
用户昵称 Kulliu 运行时间 2.118 s
代码语言 C++ 内存使用 1.07 MiB
提交时间 2016-10-15 16:53:30
显示代码纯文本
/*************************
 Personal idea of level-1
**************************/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
#define INF 0x7fffffff
typedef long long LL;
const int SIZE = 100010;

int fa[SIZE],m,n,node[SIZE];//fmax[SIZE][SIZE],fmin[SIZE][SIZE];

int find(int x){
    if(fa[x]!=x)
        return fa[x]=find(fa[x]);
    return x;
}

void Union(int u,int v){
    int fu=find(u),fv=find(v);
    fa[fu]=fv;
}

void init(){
    int s,e;
    //memset(fmin,0x7f,sizeof(fmin));
    scanf("%d",&n);
    //scanf("%d",&node[i]);fmax[1][1]=fmin[1][1]=node[1];
    for(int i=1;i<=n;i++)scanf("%d",&node[i]),fa[i]=i;
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&s,&e);
        int max=0,min=INF;
        for(int j=s;j<=e;j++){
            if(node[j]>max)max=node[j];
            if(node[j]<min)min=node[j];
        }
		Union(max,min);
    }
}

int main(){
	freopen("basicgraph.in","r",stdin);
	freopen("basicgraph.out","w",stdout);
    int k,x,y;
    init();
    scanf("%d",&k);
    while(k--)
    {
        scanf("%d%d",&x,&y);
        if(find(x)==find(y))printf("YES\n");
        else printf("NO\n");
    }
    fclose(stdin);fclose(stdout);
    return 0;
}