Art_Uspen

Untitled

Sep 28th, 2021
972
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. struct Request {
  10.     Request() = default;
  11.  
  12.     Request(int l, int r) : left(l), right(r) {}
  13.  
  14.     int left;
  15.     int right;
  16. };
  17.  
  18.  
  19. using namespace std;
  20.  
  21. int n;
  22. vector<int> a;     //массив
  23. vector<int> tree(400004);  //дерево отрезков. в вершинах хранятся минимумы
  24.  
  25. void build_tree(int v, int tl, int tr) {
  26.     if (tl == tr) {
  27.         tree[v] = a[tl];
  28.     } else {
  29.         int tm = (tl + tr) / 2;
  30.         build_tree(v * 2 + 1, tl, tm);
  31.         build_tree(v * 2 + 2, tm + 1, tr);
  32.         tree[v] = min(tree[v * 2 + 1], tree[v * 2 + 2]);    //сохраняем минимум вместо суммы
  33.     }
  34. }
  35.  
  36. //Запрос минимума
  37. int get_min(int l, int r, int v, int tl, int tr) {
  38.     //вариант 1
  39.     if (l <= tl && tr <= r) {
  40.         return tree[v];
  41.     }
  42.  
  43.     //вариант 2
  44.     if (tr < l || r < tl) {
  45.         return INT64_MAX;     //Значение, которое не повлияет на общий минимум
  46.     }
  47.  
  48.     //вариант 3
  49.     int tm = (tl + tr) / 2;
  50.     return min(get_min(l, r, v * 2 + 1, tl, tm),    //минимум вместо суммы.
  51.                get_min(l, r, v * 2 + 2, tm + 1, tr));
  52. }
  53.  
  54.  
  55. int start_get(const Request &req) {
  56.     int R_i = req.right - 1;
  57.     int L_i = req.left;
  58.     auto tmp = get_min(L_i,R_i, 0, 0, a.size() - 1);
  59.     return get_min(L_i,R_i, 0, 0, a.size() - 1);
  60. }
  61.  
  62. vector<int> ProcessRequests(const vector<int> &numbers, const vector<Request> &requests) {
  63.     a = numbers;
  64.     build_tree(0, 0, numbers.size() - 1);
  65.     vector<int> res;
  66.     res.resize(requests.size());
  67.     transform(par, requests.begin(), requests.end(), res.begin(), start_get);
  68.     return res;
  69. }
  70.  
  71. int main() {
  72.     const vector<int> numbers = {3, 1, 0, 4};
  73.     const vector<Request> requests = {
  74.             {0, 4},
  75.             {0, 2},
  76.             {1, 3},
  77.             {3, 4}
  78.     };
  79.     for (int result: ProcessRequests(numbers, requests)) {
  80.         cout << result << " ";
  81.     }
  82.     cout << endl;
  83. }
  84.  
  85.  
RAW Paste Data