比赛 |
防止浮躁的小练习v0.5 |
评测结果 |
AAAAAAA |
题目名称 |
基本的图问题 |
最终得分 |
100 |
用户昵称 |
AntiLeaf |
运行时间 |
1.503 s |
代码语言 |
C++ |
内存使用 |
25.96 MiB |
提交时间 |
2016-10-15 18:39:09 |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=150010;
void RMQ_init();//Sparse-Table
int RMQ_min(int,int);
int RMQ_max(int,int);
int log2(int);
int findroot(int);//Union-Find
void mergeset(int,int);
int a[maxn],mn[maxn][30],mx[maxn][30],prt[maxn],size[maxn];
int n,m,l,r,x,y;
int main(){
#define MINE
#ifdef MINE
freopen("basicgraph.in","r",stdin);
freopen("basicgraph.out","w",stdout);
#endif
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
prt[i]=i;
size[i]=1;
}
RMQ_init();
scanf("%d",&m);
while(m--){
scanf("%d%d",&l,&r);
x=RMQ_min(l,r);
y=RMQ_max(l,r);
mergeset(x,y);
}
scanf("%d",&m);
while(m--){
scanf("%d%d",&x,&y);
printf(findroot(x)==findroot(y)?"YES\n":"NO\n");
}
#ifndef MINE
printf("\n--------------------DONE--------------------\n");
for(;;);
#endif
return 0;
}
void RMQ_init(){
for(int i=1;i<=n;i++)mn[i][0]=mx[i][0]=a[i];
for(int j=1;(1<<j)<=n;j++)for(int i=1;i+(j<<1)-1<=n;i++){
mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
}
}
int RMQ_min(int l,int r){
int k=log2(r-l+1);
return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
int RMQ_max(int l,int r){
int k=log2(r-l+1);
return max(mx[l][k],mx[r-(1<<k)+1][k]);
}
inline int log2(int x){
int i=-1;
while(x){
x>>=1;
i++;
}
return i;
}
int findroot(int x){
int rt=prt[x],y;
while(prt[rt]!=rt)rt=prt[rt];
while(prt[x]!=x){
y=prt[x];
prt[x]=rt;
x=y;
}
return rt;
}
void mergeset(int x,int y){
int rx=findroot(x),ry=findroot(y);
if(rx==ry)return;
if(size[rx]>size[ry])swap(rx,ry);
prt[rx]=ry;
size[ry]+=size[rx];
}