Art_Uspen

Untitled

Sep 28th, 2021
911
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. #include <bits/stdc++.h>
  22.  
  23. using namespace std;
  24.  
  25. int n;
  26. vector<int> a;     //массив
  27. vector<int> tree(1e9);  //дерево отрезков. в вершинах хранятся минимумы
  28.  
  29. void build_tree(int v, int tl, int tr) {
  30.     if (tl == tr) {
  31.         tree[v] = a[tl];
  32.     } else {
  33.         int tm = (tl + tr) / 2;
  34.         build_tree(v * 2, tl, tm);
  35.         build_tree(v * 2 + 1, tm + 1, tr);
  36.         tree[v] = min(tree[v * 2], tree[v * 2 + 1]);    //сохраняем минимум вместо суммы
  37.     }
  38. }
  39.  
  40. //Запрос минимума
  41. int get_min(int l, int r, int v, int tl, int tr) {
  42.     //вариант 1
  43.     if (l <= tl && tr <= r) {
  44.         return tree[v];
  45.     }
  46.  
  47.     //вариант 2
  48.     if (tr < l || r < tl) {
  49.         return INT_MAX;     //Значение, которое не повлияет на общий минимум
  50.     }
  51.  
  52.     //вариант 3
  53.     int tm = (tl + tr) / 2;
  54.     return min(get_min(l, r, v * 2, tl, tm),    //минимум вместо суммы.
  55.                get_min(l, r, v * 2 + 1, tm + 1, tr));
  56. }
  57.  
  58. void update(int idx, int val, int v, int tl, int tr) {
  59.     //вариант 1
  60.     if (idx <= tl && tr <= idx) {       //То же, что и idx == tl == tr
  61.         a[idx] = val;
  62.         tree[v] = val;
  63.         return;
  64.     }
  65.  
  66.     //вариант 2
  67.     if (tr < idx || idx < tl) {
  68.         return;
  69.     }
  70.  
  71.     //вариант 3
  72.     int tm = (tl + tr) / 2;
  73.     update(idx, val, v * 2, tl, tm);
  74.     update(idx, val, v * 2 + 1, tm + 1, tr);
  75.     tree[v] = min(tree[v * 2], tree[v * 2 + 1]);    //минимум вместо суммы.
  76. }
  77.  
  78. int start_get(const Request &req) {
  79.     int R_i = req.right - 1;
  80.     int L_i = req.left;
  81.     auto tmp = get_min(R_i, L_i, 1, 0, a.size() - 1);
  82.     return get_min(R_i, L_i, 1, 0, a.size() - 1);
  83. }
  84.  
  85. vector<int> ProcessRequests(const vector<int> &numbers, const vector<Request> &requests) {
  86.     a = numbers;
  87.     build_tree(1, 0, numbers.size() - 1);
  88.     vector<int> res;
  89.     res.resize(requests.size());
  90.     transform(par, requests.begin(), requests.end(), res.begin(), start_get);
  91.     return res;
  92. }
  93.  
  94. int main() {
  95.     const vector<int> numbers = {3, 1, 0, 4};
  96.     const vector<Request> requests = {
  97.             {0, 4},
  98.             {0, 2},
  99.             {1, 3},
  100.             {3, 4}
  101.     };
  102.     for (int result: ProcessRequests(numbers, requests)) {
  103.         cout << result << " ";
  104.     }
  105.     cout << endl;
  106. }
  107.  
RAW Paste Data