比赛 |
防止浮躁的小练习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);
- }