比赛 |
防止浮躁的小练习v0.5 |
评测结果 |
AAWWAWW |
题目名称 |
基本的图问题 |
最终得分 |
42 |
用户昵称 |
dududu |
运行时间 |
0.620 s |
代码语言 |
C++ |
内存使用 |
8.32 MiB |
提交时间 |
2016-10-15 18:29:07 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define KN 100010
#define L(i) i<<1
#define R(i) (i<<1)+1
#define inf 100010
#define KM 500010
int getnum()
{
int res=0;
char tmp=getchar();
while(tmp<'0'||tmp>'9') tmp=getchar();
while(tmp<='9'&&tmp>='0')
{
res=res*10+tmp-'0';
tmp=getchar();
}
return res;
}
inline int min(int a,int b)
{
return a<b? a:b;
}
inline int max(int a,int b)
{
return a>b? a:b;
}
struct node
{
int l,r,mid,min_v,max_v;
node(){
l=r=mid=min_v=max_v=0;
}
};
int N,M,K,XDD;
struct Tree
{
node data[KN*4];
void build(int L,int R,int i)
{
int mid=(L+R)>>1;
data[i].mid=mid;
data[i].l=L;
data[i].r=R;
data[i].max_v=-1;
data[i].min_v=inf;
if(L==R) return;
build(L,mid,L(i));
build(mid+1,R,R(i));
}
void updata(int now,int i)
{
// printf("%d %d %d %d\n",data[i].l,data[i].r,data[i].mid,i);
data[i].max_v=max(data[i].max_v,XDD);
data[i].min_v=min(data[i].min_v,XDD);
if(data[i].l==data[i].r) return;
if(now<=data[i].mid) updata(now,L(i));
else updata(now,R(i));
}
int min_query(int l,int r,int i)
{
int L=data[i].l,R=data[i].r,mid=data[i].mid;
if(l==L&&r==R) return data[i].min_v;
if(r<=mid) return min_query(l,r,L(i));
else if(l>mid) return min_query(l,r,R(i));
else return min(min_query(l,mid,L(i)),min_query(mid+1,r,R(i)));
}
int max_query(int l,int r,int i)
{
int L=data[i].l,R=data[i].r,mid=data[i].mid;
if(l==L&&r==R) return data[i].max_v;
if(r<=mid) return max_query(l,r,L(i));
else if(l>mid) return max_query(l,r,R(i));
else return max(max_query(l,mid,L(i)),max_query(mid+1,r,R(i)));
}
}T;
int f[KN];
int getfa(int dudu)
{
return f[dudu]= dudu==f[dudu]? dudu:getfa(f[dudu]);
}
void init()
{
cin>>N;
T.build(1,N,1);
for(int i=1;i<=N;i++) f[i]=i,XDD=getnum(),T.updata(i,1);
cin>>M;
for(int i=1,l,r;i<=M;i++)
{
l=getnum(),r=getnum();
f[T.min_query(l,r,1)]=T.max_query(l,r,1);
}
cin>>K;
for(int i=1,u,v;i<=K;i++)
{
u=getnum(),v=getnum();
if(getfa(u)==getfa(v)) puts("YES");
else puts("NO");
}
}
int main()
{
freopen("basicgraph.in","r",stdin);
freopen("basicgraph.out","w",stdout);
init();
return 0;
}