JacobianDet

Untitled

May 19th, 2018
263
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.20 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define MV 300001
  3. #define pb push_back
  4.  
  5. struct cap
  6. {
  7. int lb, rb, md;
  8. std::map<int, int> ctr;
  9. }seg[4*MV];
  10.  
  11. int arr[MV];
  12. std::vector<int> Z;
  13.  
  14. class segtree
  15. {
  16. public: void build(int i, int s, int d);
  17. cap merger(cap left, cap right);
  18. void update(int i, int s, int d, int x, int y);
  19. void query(int i, int s, int d, int qs, int qd);
  20. };
  21.  
  22. void segtree::build(int i, int s, int d)
  23. {
  24. if(s == d)
  25. {
  26. seg[i].lb = s;
  27. seg[i].rb = d;
  28. seg[i].md = arr[s];
  29. seg[i].ctr[arr[s]]++;
  30. return;
  31. }
  32. int m = (s + d)/2;
  33. build(2*i, s, m);
  34. build(2*i+1, m+1, d);
  35. seg[i] = merger(seg[2*i], seg[2*i+1]);
  36. return;
  37. }
  38.  
  39. cap segtree::merger(cap left, cap right)
  40. {
  41. cap res;
  42. if(!left.lb)
  43. {
  44. res.lb = right.lb;
  45. res.rb = right.rb;
  46. }
  47. else if(!right.lb)
  48. {
  49. res.lb = left.lb;
  50. res.rb = left.rb;
  51. }
  52. else
  53. {
  54. res.lb = left.lb;
  55. res.rb = right.rb;
  56. }
  57. res.ctr.insert(left.ctr.begin(), left.ctr.end());
  58. for(std::map<int, int>::iterator it = right.ctr.begin();it != right.ctr.end();it++)
  59. res.ctr[it->first] += right.ctr[it->first];
  60. res.md = 0;
  61. if(left.md)
  62. {
  63. if((res.ctr[left.md])*2 > (res.rb - res.lb + 1))
  64. res.md = left.md;
  65. }
  66. if(right.md)
  67. {
  68. if((res.ctr[right.md])*2 > (res.rb - res.lb + 1))
  69. res.md = right.md;
  70. }
  71. return res;
  72. }
  73.  
  74. void segtree::query(int i, int s, int d, int qs, int qd)
  75. {
  76. if(s > qd || d < qs)
  77. return;
  78. if(qs <= s && d <= qd)
  79. {
  80. Z.pb(i);
  81. return;
  82. }
  83. int m = (s + d)/2;
  84. query(2*i, s, m, qs, qd);
  85. query(2*i+1, m+1, d, qs, qd);
  86. return;
  87. }
  88.  
  89. int main(void)
  90. {
  91. std::ios_base::sync_with_stdio(false);
  92. std::cin.tie(NULL);
  93. std::cout.tie(NULL);
  94. int n,c;
  95. std::cin>>n>>c;
  96. for(int i=1;i<=n;i++)
  97. std::cin>>arr[i];
  98. segtree T;
  99. T.build(1, 1, n);
  100. int q;
  101. std::cin>>q;
  102. while(q--)
  103. {
  104. Z.clear();
  105. int l,r;
  106. std::cin>>l>>r;
  107. T.query(1, 1, n, l, r);
  108. bool ok = 0;
  109. for(int i=0,t=(int)Z.size();i<t;i++)
  110. {
  111. int ct = 0;
  112. if(seg[Z[i]].md)
  113. {
  114. for(int j=0;j<t;j++)
  115. ct += seg[Z[j]].ctr[seg[Z[i]].md];
  116. }
  117. if(ct*2 > (r-l+1))
  118. {
  119. std::cout<<"yes "<<seg[Z[i]].md<<"\n";
  120. ok = 1;
  121. break;
  122. }
  123. }
  124. if(!ok)
  125. std::cout<<"no\n";
  126. }
  127. return 0;
  128. }
Add Comment
Please, Sign In to add comment