Art_Uspen

Untitled

Sep 28th, 2021
914
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <vector>
  2. #include <cmath>
  3. #include <execution>
  4. #include<iostream>
  5.  
  6. using namespace std;
  7. using namespace std::execution;
  8.  
  9. vector<vector<int>> st;
  10. vector<int> degrees;
  11.  
  12. struct Request {
  13.     Request() = default;
  14.  
  15.     Request(int l, int r) : left(l), right(r) {}
  16.  
  17.     int left;
  18.     int right;
  19. };
  20.  
  21.  
  22. using namespace std;
  23.  
  24. int n;
  25. vector<int> a;     //массив
  26. vector<int> tree(1e9);  //дерево отрезков. в вершинах хранятся минимумы
  27.  
  28. void build_tree(int v, int tl, int tr) {
  29.     if (tl == tr) {
  30.         tree[v] = a[tl];
  31.     } else {
  32.         int tm = (tl + tr) / 2;
  33.         build_tree(v * 2 + 1, tl, tm);
  34.         build_tree(v * 2 + 2, tm + 1, tr);
  35.         tree[v] = min(tree[v * 2 + 1], tree[v * 2 + 2]);    //сохраняем минимум вместо суммы
  36.     }
  37. }
  38.  
  39. //Запрос минимума
  40. int get_min(int l, int r, int v, int tl, int tr) {
  41.     //вариант 1
  42.     if (l <= tl && tr <= r) {
  43.         return tree[v];
  44.     }
  45.  
  46.     //вариант 2
  47.     if (tr < l || r < tl) {
  48.         return INT64_MAX;     //Значение, которое не повлияет на общий минимум
  49.     }
  50.  
  51.     //вариант 3
  52.     int tm = (tl + tr) / 2;
  53.     return min(get_min(l, r, v * 2 + 1, tl, tm),    //минимум вместо суммы.
  54.                get_min(l, r, v * 2 + 2, tm + 1, tr));
  55. }
  56.  
  57. void update(int idx, int val, int v, int tl, int tr) {
  58.     //вариант 1
  59.     if (idx <= tl && tr <= idx) {       //То же, что и idx == tl == tr
  60.         a[idx] = val;
  61.         tree[v] = val;
  62.         return;
  63.     }
  64.  
  65.     //вариант 2
  66.     if (tr < idx || idx < tl) {
  67.         return;
  68.     }
  69.  
  70.     //вариант 3
  71.     int tm = (tl + tr) / 2;
  72.     update(idx, val, v * 2, tl, tm);
  73.     update(idx, val, v * 2 + 1, tm + 1, tr);
  74.     tree[v] = min(tree[v * 2], tree[v * 2 + 1]);    //минимум вместо суммы.
  75. }
  76.  
  77. int start_get(const Request &req) {
  78.     int R_i = req.right - 1;
  79.     int L_i = req.left;
  80. //    auto tmp = get_min(R_i, L_i, 1, 0, a.size() - 1);
  81.     return get_min(R_i, L_i, 0, 0, a.size() - 1);
  82. }
  83.  
  84. vector<int> ProcessRequests(const vector<int> &numbers, const vector<Request> &requests) {
  85.     a = numbers;
  86.     build_tree(1, 0, numbers.size() - 1);
  87.     vector<int> res;
  88.     res.resize(requests.size());
  89.     transform(par, requests.begin(), requests.end(), res.begin(), start_get);
  90.     return res;
  91.  
RAW Paste Data