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