Advertisement
KShah

Untitled

Nov 21st, 2021
56
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <vector>
  2. #include <iostream>
  3. #include <cassert>
  4. #include <climits>
  5. // 13 = 8 + 4 + 1 0:00001101 1:00000110 2:00000011 3:00000001 4:00000000
  6. int next_2_degree(int value)
  7. {
  8. int i = 0;
  9. while(value >> i) ++i;
  10.  
  11. return 1 << i;
  12. }
  13.  
  14. //-----------------------------------------------------------------------------
  15.  
  16. class MinSegmentTree {
  17. public:
  18. MinSegmentTree(const std::vector<int>& arr, int defaultValue);
  19.  
  20. int GetMin(int left, int right) const;
  21. void Update(int val, int pos);
  22. private:
  23. std::vector<int> min_;
  24. int default_;
  25.  
  26. void build(int index, int left, int right);
  27. void update(int index, int left, int right, int val, int pos);
  28. int getMin(int index, int i_left, int i_right, int left, int right) const;
  29. };
  30.  
  31. MinSegmentTree::MinSegmentTree(const std::vector<int>& arr, int defaultValue)
  32. : min_(next_2_degree(arr.size()) * 2, defaultValue),
  33. default_(defaultValue) {
  34. // Предзаполняем последний слой дерева отрезков
  35. std::copy(arr.begin(), arr.end(), min_.begin() + min_.size() / 2 - 1);
  36. build(0, 0, min_.size() / 2 - 1);
  37. }
  38.  
  39. void MinSegmentTree::build(int index, int left, int right) {
  40. if (left == right) return;
  41.  
  42. const int mid = (left + right) >> 1;
  43. build(2 * index + 1, left, mid);
  44. build(2 * index + 2, mid + 1, right);
  45. min_[index] = std::min(min_[2 * index + 1], min_[2 * index + 2]);
  46. }
  47.  
  48. void MinSegmentTree::Update(int val, int pos) {
  49. update(0, 0, min_.size() / 2 - 1, val, pos);
  50. return;
  51. }
  52.  
  53. void MinSegmentTree::update(int index, int left, int right, int val, int pos) {
  54. if (left == right) {
  55. min_[index] = val;
  56. return;
  57. }
  58.  
  59. const int mid = (left + right) >> 1;
  60. if (pos <= mid) {
  61. update(2 * index + 1, left, mid, val, pos);
  62. }
  63. if (pos > mid) {
  64. update(2 * index + 2, mid + 1, right, val, pos);
  65. }
  66. min_[index] = std::min(min_[2 * index + 1], min_[2 * index + 2]);
  67.  
  68. }
  69.  
  70. int MinSegmentTree::GetMin(int left, int right) const {
  71. return getMin(0, 0, min_.size() / 2 - 1, left, right);
  72. }
  73.  
  74. int MinSegmentTree::getMin(int index, int i_left, int i_right, int left, int right) const {
  75. assert(i_left <= i_right && left <= right);
  76. // Пересечения нет. Отрезок левее
  77. if (right < i_left) { return default_; }
  78. // Пересечения нет. Отрезок правее
  79. if (i_right < left) { return default_; }
  80.  
  81. if (left <= i_left && i_right <= right) {
  82. return min_[index];
  83. }
  84.  
  85. const int mid = (i_left + i_right) / 2;
  86. return std::min(getMin(2 * index + 1, i_left, mid, left, right),
  87. getMin(2 * index + 2, mid + 1, i_right, left, right));
  88. }
  89.  
  90.  
  91. //-----------------------------------------------------------------------------
  92.  
  93. class MaxSegmentTree {
  94. public:
  95. MaxSegmentTree(const std::vector<int>& arr, int defaultValue);
  96.  
  97. int GetMax(int left, int right) const;
  98. void Update(int val, int pos);
  99. private:
  100. std::vector <int> max_;
  101. int default_;
  102.  
  103. void build(int index, int left, int right);
  104. void update(int index, int left, int right, int val, int pos);
  105. int getMax(int index, int i_left, int i_right, int left, int right) const;
  106. };
  107.  
  108. MaxSegmentTree::MaxSegmentTree (const std::vector<int>& arr, int defaultValue)
  109. : max_(next_2_degree(arr.size()) * 2, defaultValue),
  110. default_(defaultValue) {
  111.  
  112. std::copy(arr.begin(), arr.end(), max_.begin() + max_.size() / 2 - 1);
  113. build(0, 0, max_.size() / 2 - 1);
  114. }
  115.  
  116. void MaxSegmentTree::build(int index, int left, int right) {
  117. if (left == right) return;
  118.  
  119. const int mid = (left + right) >> 1;
  120. build(2 * index + 1, left, mid);
  121. build(2 * index + 2, mid + 1, right);
  122. max_[index] = std::max(max_[2 * index + 1], max_[2 * index + 2]);
  123. }
  124.  
  125. void MaxSegmentTree::Update(int val, int pos) {
  126. update(0, 0, max_.size() / 2 - 1, val, pos);
  127. return;
  128. }
  129.  
  130. void MaxSegmentTree::update(int index, int left, int right, int val, int pos) {
  131. if (left == right) {
  132. max_[index] = val;
  133. return;
  134. }
  135.  
  136. const int mid = (left + right) >> 1;
  137. if (pos <= mid) {
  138. update(2 * index + 1, left, mid, val, pos);
  139. }
  140. if (pos > mid) {
  141. update(2 * index + 2, mid + 1, right, val, pos);
  142. }
  143. max_[index] = std::max(max_[2 * index + 1], max_[2 * index + 2]);
  144. }
  145.  
  146. int MaxSegmentTree::GetMax(int left, int right) const {
  147. return getMax(0, 0, max_.size() / 2 - 1, left, right);
  148. }
  149.  
  150. int MaxSegmentTree::getMax(int index, int i_left, int i_right, int left, int right) const {
  151. assert(i_left <= i_right && left <= right);
  152.  
  153. if (right < i_left) { return default_; }
  154. if (left > i_right) { return default_; }
  155.  
  156. if (left <= i_left && i_right <= right) {
  157. return max_[index];
  158. }
  159.  
  160.  
  161. const int mid = (i_left + i_right) / 2;
  162. return std::max(getMax(2 * index + 1, i_left, mid, left, right),
  163. getMax(2 * index + 2, mid + 1, i_right, left, right));
  164.  
  165. }
  166.  
  167. //-----------------------------------------------------------------------------
  168.  
  169. int main() {
  170. int n = 100000;
  171. std::vector<int> arr(n, 0);
  172. for (int i = 1; i <= n; ++i) {
  173. int fst = (i % 12345 * i % 12345) % 12345,
  174. snd = (i % 23456 * i % 23456 * i % 23456) % 23456;
  175. arr[i - 1] = fst + snd;
  176. }
  177. MinSegmentTree minTree(arr, INT_MAX);
  178. MaxSegmentTree maxTree(arr, INT_MIN);
  179.  
  180. int k;
  181. std::cin >> k;
  182. for (int i = 0; i < k; ++i) {
  183. int x, y;
  184. std::cin >> x >> y;
  185. if (x > 0) {
  186. --x;
  187. --y;
  188. std::cout << maxTree.GetMax(x, y) - minTree.GetMin(x, y) << '\n';
  189. } else {
  190. x *= -1;
  191. --x;
  192. maxTree.Update(y, x);
  193. minTree.Update(y, x);
  194. }
  195. }
  196. return 0;
  197. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement