比赛 |
20160909 |
评测结果 |
AAAAAAA |
题目名称 |
基本的图问题 |
最终得分 |
100 |
用户昵称 |
Mealy |
运行时间 |
1.927 s |
代码语言 |
C++ |
内存使用 |
68.95 MiB |
提交时间 |
2016-09-09 20:28:57 |
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
const int nmax=500086;
const int vmax=20;
int n,op,q;
int tmpl,tmpr;
int tmpmax,tmpmin;
int r[nmax];
int unp[nmax];
int arrrmqmin[nmax][vmax];
int arrrmqmax[nmax][vmax];
void PreDowithSetSet()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&r[i]);
unp[i]=i;
}
}
void PreRMQ()
{
for(int i=1;i<=n;i++)
{
arrrmqmax[i][0]=r[i];
arrrmqmin[i][0]=r[i];
}
}
void RMQ()
{
for(int j=1;j<20;j++)
for(int i=1;i<=n;i++)
if(i+(1<<j)-1<=n)
{
arrrmqmin[i][j]=min(arrrmqmin[i][j-1],arrrmqmin[i+(1<<(j-1))][j-1]);
arrrmqmax[i][j]=max(arrrmqmax[i][j-1],arrrmqmax[i+(1<<(j-1))][j-1]);
}
}
int GetMin(int l,int r)
{
int k=int(floor(log2(r-l+1)));
return min(arrrmqmin[l][k],arrrmqmin[r-(1<<k)+1][k]);
}
int GetMax(int l,int r)
{
int k=int(floor(log2(r-l+1)));
return max(arrrmqmax[l][k],arrrmqmax[r-(1<<k)+1][k]);
}
int SetFind(int a)
{
if(a==unp[a])
return a;
unp[a]=SetFind(unp[a]);
return unp[a];
}
void SetMerge(int x,int y)
{
int px=SetFind(x);
int py=SetFind(y);
unp[px]=py;
}
int main()
{
freopen("basicgraph.in","r",stdin);
freopen("basicgraph.out","w",stdout);
PreDowithSetSet();
PreRMQ();
RMQ();
scanf("%d",&op);
for(int i=1;i<=op;i++)
{
scanf("%d%d",&tmpl,&tmpr);
tmpmin=GetMin(tmpl,tmpr);
tmpmax=GetMax(tmpl,tmpr);
SetMerge(tmpmin,tmpmax);
}
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%d%d",&tmpl,&tmpr);
if(SetFind(tmpl)==SetFind(tmpr))
printf("YES\n");
else
printf("NO\n");
}
return 0;
}