比赛 |
20160909 |
评测结果 |
AAAEAAE |
题目名称 |
基本的图问题 |
最终得分 |
71 |
用户昵称 |
ミント |
运行时间 |
0.954 s |
代码语言 |
C++ |
内存使用 |
11.08 MiB |
提交时间 |
2016-09-09 21:02:57 |
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 50000 + 100;
int st[maxn][32][2];
int num[maxn], n;
int ufs[maxn];
void Init(){
memset(st, 0, sizeof(st));
memset(num, 0, sizeof(num));
for(int i=0;i<maxn;i++)ufs[i] = i;
return ;
}
void make(int flag){
for(int i=1;i<=n;i++)
st[i][0][flag] = num[i];
for(int i=1;(1<<i)<=n;i++)
for(int j=1;j+(1<<i)-1<=n;j++){
if(!flag)st[j][i][flag] = max(st[j][i-1][flag], st[j+(1<<(i-1))][i-1][flag]);
else st[j][i][flag] = min(st[j][i-1][flag], st[j+(1<<(i-1))][i-1][flag]);
}
return ;
}
inline int q(int l, int r, int flag){
int k = 0;
while((1<<(k+1))<=r-l+1)k++;
if(!flag)return max(st[l][k][flag], st[r-(1<<k)+1][k][flag]);
else return min(st[l][k][flag], st[r-(1<<k)+1][k][flag]);
}
inline int find(int x){
if(ufs[x]!=x)return ufs[x] = find(ufs[x]);
return ufs[x];
}
inline void merge(int x, int y){
ufs[find(x)] = find(y);
return ;
}
int main(){
freopen("basicgraph.in", "r", stdin);
freopen("basicgraph.out", "w", stdout);
Init();
cin>>n;
for(int i=1;i<=n;i++)cin>>num[i];
make(0);make(1);
int m;cin>>m;
while(m--){
int a, b;cin>>a>>b;
int mx = q(a, b, 0), mn = q(a, b, 1);
merge(mx, mn);
//cout<<mx<<' '<<mn<<endl;
}
int k;cin>>k;
while(k--){
int a, b;cin>>a>>b;
if(find(a)==find(b))cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}