比赛 |
防止浮躁的小练习v0.5 |
评测结果 |
AAWWAWW |
题目名称 |
基本的图问题 |
最终得分 |
42 |
用户昵称 |
jmisnal |
运行时间 |
0.658 s |
代码语言 |
C++ |
内存使用 |
16.34 MiB |
提交时间 |
2016-10-15 16:37:33 |
显示代码纯文本
- #include <iostream>
- #include <cstdio>
- using namespace std;
- int n,m,Q;
- int a[100050],dx[100050][20],dd[100050][20];
- void init()
- {
- for(int i=1;i<=n;i++)
- dx[i][0]=dd[i][0]=a[i];
- for(int j=1;(1<<j)<=n;j++)
- {
- for(int i=1;i+(1<<j)-1<=n;i++)
- {
- dx[i][j]=min(dx[i][j-1],dx[i+(1<<(j-1))][j-1]);
- dd[i][j]=max(dd[i][j-1],dd[i+(1<<(j-1))][j-1]);
- // cout<<i<<' '<<i+(1<<j)<<' '<<d[i][j]<<endl;
- }
- }
-
- }
- int rminq(int l,int r)
- {
- int k=0;
- while((1<<(k+1))<=r-l)k++;
- return min(dx[l][k],dx[r-(1<<k)+1][k]);
- }
- int rmaxq(int l,int r)
- {
- int k=0;
- while((1<<(k+1))<=r-l)k++;
- // cout<<k<<' '<<d[l][k]<<' '<<d[r-(1<<k)][k];
- return max(dd[l][k],dd[r-(1<<k)+1][k]);
- }
- int fa[100050];
- int find(int x)
- {
- int t=x;
- while(fa[t]!=t)
- t=fa[t];
- return t;
- }
- int main()
- {
- freopen("basicgraph.in","r",stdin);
- freopen("basicgraph.out","w",stdout);
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- {
- scanf("%d",&a[i]);
- fa[i]=i;
- }
- init();
- // return 0;
- scanf("%d",&m);
- int l,r,x1,x2;
-
- for(int i=1;i<=m;i++)
- {
- scanf("%d%d",&l,&r);
- x1=rminq(l,r),x2=rmaxq(l,r);
- // cout<<x1<<' '<<x2<<endl;
- fa[x1]=x2;
- }
- scanf("%d",&Q);
- for(int i=1;i<=Q;i++)
- {
- scanf("%d%d",&l,&r);
- if(find(l)==find(r))
- printf("YES\n");
- else printf("NO\n");
- }
- return 0;
- }