比赛 防止浮躁的小练习v0.5 评测结果 AAAAAAA
题目名称 基本的图问题 最终得分 100
用户昵称 _Itachi 运行时间 0.853 s
代码语言 C++ 内存使用 5.25 MiB
提交时间 2016-10-15 15:36:28
显示代码纯文本
  1. #include<cstdio>
  2. #include<cmath>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. int n, m, k;
  7. int root[100100];
  8. int tree[400100], minn[400100], maxn[400100];
  9. template <class T> inline void _read(T& a){
  10. a = 0;
  11. char ch = getchar();
  12. while(ch < '0' || ch > '9') ch = getchar();
  13. while(ch >= '0' && ch <= '9'){
  14. a = a * 10 + ch - '0';
  15. ch = getchar();
  16. }
  17. }
  18. int _find(const int& a){
  19. if(root[a] != a) root[a] = _find(root[a]);
  20. return root[a];
  21. }
  22. inline void Union(const int& a, const int& b){
  23. int ra = _find(a), rb = _find(b);
  24. root[ra] = rb;
  25. }
  26. void Build(const int& l, const int& r, const int& rt){
  27. if(l == r){
  28. _read(tree[rt]);
  29. maxn[rt] = minn[rt] = tree[rt];
  30. return;
  31. }
  32. const int mid = (l + r) >> 1, lch = rt << 1, rch = (rt << 1) | 1;
  33. Build(l, mid, lch);
  34. Build(mid+1, r, rch);
  35. tree[rt] = tree[lch] + tree[rch];
  36. minn[rt] = min(minn[lch], minn[rch]);
  37. maxn[rt] = max(maxn[lch], maxn[rch]);
  38. }
  39. int _getmin(const int& l, const int& r, const int& s, const int& t, const int& rt){
  40. if(l >= s && r <= t) return minn[rt];
  41. const int mid = (l + r) >> 1, lch = rt << 1, rch = (rt << 1) | 1;
  42. if(t <= mid) return _getmin(l, mid, s, t, lch);
  43. else if(s >= mid+1) return _getmin(mid+1, r, s, t, rch);
  44. return min(_getmin(l, mid, s, mid, lch), _getmin(mid+1, r, mid+1, t, rch));
  45. }
  46. int _getmax(const int& l, const int& r, const int& s, const int& t, const int& rt){
  47. if(l >= s && r <= t) return maxn[rt];
  48. const int mid = (l + r) >> 1, lch = rt << 1, rch = (rt << 1) | 1;
  49. if(t <= mid) return _getmax(l, mid, s, t, lch);
  50. else if(s >= mid+1) return _getmax(mid+1, r, s, t, rch);
  51. return max(_getmax(l, mid, s, mid, lch), _getmax(mid+1, r, mid+1, t, rch));
  52. }
  53. void _work(){
  54. _read(n);
  55. for(int i = 1; i <= n; i++) root[i] = i;
  56. memset(minn, 0x7f, sizeof(minn));
  57. Build(1, n, 1);
  58. _read(m);
  59. int l, r;
  60. for(int i = 1; i <= m; i++){
  61. _read(l); _read(r);
  62. Union(_getmin(1, n, l, r, 1), _getmax(1, n, l, r, 1));
  63. }
  64. _read(k);
  65. int s, t;
  66. for(int i = 1; i <= k; i++){
  67. _read(s); _read(t);
  68. if(_find(s) == _find(t)) puts("YES");
  69. else puts("NO");
  70. }
  71. }
  72. int main(){
  73. #define _Rabit _RABIT
  74. #ifdef _Rabit
  75. freopen("basicgraph.in","r",stdin);
  76. freopen("basicgraph.out","w",stdout);
  77. #endif
  78. _work();
  79. #ifndef _Rabit
  80. getchar(),getchar();
  81. #endif
  82. fclose(stdin);fclose(stdout);
  83. }