比赛 防止浮躁的小练习v0.5 评测结果 AAWWAWW
题目名称 基本的图问题 最终得分 42
用户昵称 jmisnal 运行时间 0.658 s
代码语言 C++ 内存使用 16.34 MiB
提交时间 2016-10-15 16:37:33
显示代码纯文本
  1. #include <iostream>
  2. #include <cstdio>
  3. using namespace std;
  4. int n,m,Q;
  5. int a[100050],dx[100050][20],dd[100050][20];
  6. void init()
  7. {
  8. for(int i=1;i<=n;i++)
  9. dx[i][0]=dd[i][0]=a[i];
  10. for(int j=1;(1<<j)<=n;j++)
  11. {
  12. for(int i=1;i+(1<<j)-1<=n;i++)
  13. {
  14. dx[i][j]=min(dx[i][j-1],dx[i+(1<<(j-1))][j-1]);
  15. dd[i][j]=max(dd[i][j-1],dd[i+(1<<(j-1))][j-1]);
  16. // cout<<i<<' '<<i+(1<<j)<<' '<<d[i][j]<<endl;
  17. }
  18. }
  19.  
  20. }
  21. int rminq(int l,int r)
  22. {
  23. int k=0;
  24. while((1<<(k+1))<=r-l)k++;
  25. return min(dx[l][k],dx[r-(1<<k)+1][k]);
  26. }
  27. int rmaxq(int l,int r)
  28. {
  29. int k=0;
  30. while((1<<(k+1))<=r-l)k++;
  31. // cout<<k<<' '<<d[l][k]<<' '<<d[r-(1<<k)][k];
  32. return max(dd[l][k],dd[r-(1<<k)+1][k]);
  33. }
  34. int fa[100050];
  35. int find(int x)
  36. {
  37. int t=x;
  38. while(fa[t]!=t)
  39. t=fa[t];
  40. return t;
  41. }
  42. int main()
  43. {
  44. freopen("basicgraph.in","r",stdin);
  45. freopen("basicgraph.out","w",stdout);
  46. scanf("%d",&n);
  47. for(int i=1;i<=n;i++)
  48. {
  49. scanf("%d",&a[i]);
  50. fa[i]=i;
  51. }
  52. init();
  53. // return 0;
  54. scanf("%d",&m);
  55. int l,r,x1,x2;
  56.  
  57. for(int i=1;i<=m;i++)
  58. {
  59. scanf("%d%d",&l,&r);
  60. x1=rminq(l,r),x2=rmaxq(l,r);
  61. // cout<<x1<<' '<<x2<<endl;
  62. fa[x1]=x2;
  63. }
  64. scanf("%d",&Q);
  65. for(int i=1;i<=Q;i++)
  66. {
  67. scanf("%d%d",&l,&r);
  68. if(find(l)==find(r))
  69. printf("YES\n");
  70. else printf("NO\n");
  71. }
  72. return 0;
  73. }