比赛 |
防止浮躁的小练习v0.5 |
评测结果 |
AAAAAAA |
题目名称 |
基本的图问题 |
最终得分 |
100 |
用户昵称 |
sxysxy |
运行时间 |
0.623 s |
代码语言 |
C++ |
内存使用 |
27.00 MiB |
提交时间 |
2016-10-15 16:32:32 |
显示代码纯文本
#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;
}