比赛 |
防止浮躁的小练习v0.5 |
评测结果 |
AAAAAAA |
题目名称 |
基本的图问题 |
最终得分 |
100 |
用户昵称 |
Smile |
运行时间 |
0.515 s |
代码语言 |
C++ |
内存使用 |
15.95 MiB |
提交时间 |
2016-10-15 19:51:04 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int maxn=100010;
const int INF=0x3f3f3f3f;
const int LOG=20;
int n, m;
vector<int> A;
int fa[maxn];
int d1[maxn][LOG];
int d2[maxn][LOG];
int MIN=INF, MAX=-INF;
int Find(int x)
{
return fa[x]==x ? x : fa[x]=Find(fa[x]);
}
void RMQ_init()
{
for(int j=1; (1<<j)<=n; j++)
for(int i=0; i+(1<<j)-1<n; i++)
d1[i][j]=min(d1[i][j-1], d1[i+(1<<(j-1))][j-1]),
d2[i][j]=max(d2[i][j-1], d2[i+(1<<(j-1))][j-1]);
}
void RMQ(int L, int R)
{
int k=0;
while(1<<(k+1) <= R-L+1) k++;
MIN=min(d1[L][k], d1[R-(1<<k)+1][k]);
MAX=max(d2[L][k], d2[R-(1<<k)+1][k]);
return;
}
int Qin()
{
int x=0;
char c=getchar();
while(c<'0' || c>'9') c=getchar();
while(c>='0' && c<='9') x=x*10+c-'0', c=getchar();
return x;
}
void init()
{
n=Qin();
for(int i=1; i<=n; i++) fa[i]=i;
for(int i=0; i<n; i++) d1[i][0]=Qin(), d2[i][0]=d1[i][0];
RMQ_init();
m=Qin();
for(int i=1; i<=m; i++) {
int S=Qin();
int E=Qin();
MIN=INF; MAX=-INF;
RMQ(S-1, E-1);
int x=Find(MIN);
int y=Find(MAX);
fa[x]=y;
}
int k=Qin();
for(int i=1; i<=k; i++) {
int u=Qin();
int v=Qin();
if(Find(u)==Find(v)) printf("YES\n");
else printf("NO\n");
}
}
int main()
{
freopen("basicgraph.in", "r", stdin);
freopen("basicgraph.out", "w", stdout);
init();
return 0;
}