比赛 |
防止浮躁的小练习v0.5 |
评测结果 |
AAAAAAA |
题目名称 |
基本的图问题 |
最终得分 |
100 |
用户昵称 |
_Itachi |
运行时间 |
0.853 s |
代码语言 |
C++ |
内存使用 |
5.25 MiB |
提交时间 |
2016-10-15 15:36:28 |
显示代码纯文本
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m, k;
int root[100100];
int tree[400100], minn[400100], maxn[400100];
template <class T> inline void _read(T& a){
a = 0;
char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9'){
a = a * 10 + ch - '0';
ch = getchar();
}
}
int _find(const int& a){
if(root[a] != a) root[a] = _find(root[a]);
return root[a];
}
inline void Union(const int& a, const int& b){
int ra = _find(a), rb = _find(b);
root[ra] = rb;
}
void Build(const int& l, const int& r, const int& rt){
if(l == r){
_read(tree[rt]);
maxn[rt] = minn[rt] = tree[rt];
return;
}
const int mid = (l + r) >> 1, lch = rt << 1, rch = (rt << 1) | 1;
Build(l, mid, lch);
Build(mid+1, r, rch);
tree[rt] = tree[lch] + tree[rch];
minn[rt] = min(minn[lch], minn[rch]);
maxn[rt] = max(maxn[lch], maxn[rch]);
}
int _getmin(const int& l, const int& r, const int& s, const int& t, const int& rt){
if(l >= s && r <= t) return minn[rt];
const int mid = (l + r) >> 1, lch = rt << 1, rch = (rt << 1) | 1;
if(t <= mid) return _getmin(l, mid, s, t, lch);
else if(s >= mid+1) return _getmin(mid+1, r, s, t, rch);
return min(_getmin(l, mid, s, mid, lch), _getmin(mid+1, r, mid+1, t, rch));
}
int _getmax(const int& l, const int& r, const int& s, const int& t, const int& rt){
if(l >= s && r <= t) return maxn[rt];
const int mid = (l + r) >> 1, lch = rt << 1, rch = (rt << 1) | 1;
if(t <= mid) return _getmax(l, mid, s, t, lch);
else if(s >= mid+1) return _getmax(mid+1, r, s, t, rch);
return max(_getmax(l, mid, s, mid, lch), _getmax(mid+1, r, mid+1, t, rch));
}
void _work(){
_read(n);
for(int i = 1; i <= n; i++) root[i] = i;
memset(minn, 0x7f, sizeof(minn));
Build(1, n, 1);
_read(m);
int l, r;
for(int i = 1; i <= m; i++){
_read(l); _read(r);
Union(_getmin(1, n, l, r, 1), _getmax(1, n, l, r, 1));
}
_read(k);
int s, t;
for(int i = 1; i <= k; i++){
_read(s); _read(t);
if(_find(s) == _find(t)) puts("YES");
else puts("NO");
}
}
int main(){
#define _Rabit _RABIT
#ifdef _Rabit
freopen("basicgraph.in","r",stdin);
freopen("basicgraph.out","w",stdout);
#endif
_work();
#ifndef _Rabit
getchar(),getchar();
#endif
fclose(stdin);fclose(stdout);
}