vadimk772336

Untitled

Dec 8th, 2021
940
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. const int MAX = 2e5;
  7.  
  8. struct vertex
  9. {
  10.     int res;
  11.     int left;
  12.     int right;
  13. };
  14.  
  15. class Segment_Tree
  16. {
  17.     struct vertex* tree;
  18.     int tree_size;
  19.     int count_numbers;
  20.     std::vector<int> numbers;
  21.  
  22. public:
  23.     void build_tree(int v, int tl, int tr);
  24.     int to_deg_of_two(std::vector<int>& numbers, int count_numbers);
  25.     void Initialize(int count_numbers);
  26.     void set(int k, int x);
  27.     int get_min(int node, int a, int b);
  28.     int find_spot(char* start_number);
  29.     int free_up(char* number);
  30.     void print_tree();
  31. };
  32.  
  33. void Segment_Tree::build_tree(int v, int tl, int tr)
  34. {
  35.  
  36.     //cout << "numbers:" << endl;
  37.     //for (int j  = 0; j < this->numbers.size(); ++j)
  38.     //    cout << numbers[j] << " ";
  39.     //cout << endl;
  40.    
  41.     if (tr - tl == 1)
  42.     {
  43.         //cout << "* tl, tr  = " << tl << " " << tr;
  44.         tree[v].res = this->numbers[tl];
  45.         tree[v].left = tl;
  46.         tree[v].right = tr;
  47.         //cout << " v = " << v <<  " tree[v] = " << tree[v].res << endl;
  48.         //print_tree();
  49.         //cout << "-------------" << endl;
  50.     }
  51.     else
  52.     {
  53.         //cout << " tl, tr  = " << tl << " " << tr << endl;
  54.         int tm = (tl + tr) / 2;
  55.         build_tree(v * 2 + 1, tl, tm);
  56.         build_tree(v * 2 + 2, tm, tr);
  57.         tree[v].left = tl;
  58.         tree[v].right = tr;
  59.  
  60.         if (tree[v * 2 + 1].res < tree[v * 2 + 2].res)
  61.             tree[v].res = tree[v * 2 + 1].res;
  62.         else
  63.             tree[v].res = tree[v * 2 + 2].res;
  64.        
  65.         //print_tree();
  66.         //cout << "-------------" << endl;
  67.         //cout << "v = " << v <<  " tree[v] = " << tree[v].res << endl;
  68.     }
  69. }
  70.  
  71. int Segment_Tree::to_deg_of_two(std::vector<int>& numbers, int count_numbers)
  72. {
  73.  
  74.     int p = 1;
  75.     while (count_numbers > p)
  76.         p *= 2;
  77.  
  78.     for (int i = 0; i < p - count_numbers; ++i)
  79.         this->numbers.push_back(MAX);
  80.  
  81.     return p;
  82. }
  83.  
  84. void Segment_Tree::Initialize(int count_numbers)
  85. {
  86.  
  87.  
  88.    
  89.     this->count_numbers = count_numbers;
  90.     this->numbers.clear();
  91.     this->numbers.resize(count_numbers);
  92.    
  93.     for (int i = 1; i <= count_numbers; ++i)
  94.         this->numbers[i-1] = i;
  95.  
  96.     this->count_numbers = to_deg_of_two(numbers, count_numbers);
  97.     this->tree_size = 2*this->count_numbers-1;
  98.     this->tree = new vertex[tree_size];
  99.     build_tree(0, 0, this->count_numbers);
  100. }
  101.  
  102.  
  103. void Segment_Tree::set(int k, int x)
  104. {
  105.     int v = this->count_numbers -1 + k;
  106.     tree[v].res = x;
  107.     while (v > 0)
  108.     {
  109.         v = (v - 1) / 2;
  110.  
  111.         int l_min = tree[2 * v + 1].res;
  112.         int r_min = tree[2 * v + 2].res;
  113.         (l_min < r_min) ? tree[v].res = l_min : tree[v].res = r_min;
  114.     }
  115. }
  116.  
  117. int Segment_Tree::get_min(int node, int a, int b)
  118. {
  119.     int l = tree[node].left;
  120.     int r = tree[node].right;
  121.     if (r <= a || l >= b)
  122.         return MAX;
  123.  
  124.     if (r < b & l >= a)
  125.         return tree[node].res;
  126.  
  127.     int m1 = get_min(node * 2 + 1, a, b);
  128.     int m2 = get_min(node * 2 + 2, a, b);
  129.     return (m1 < m2) ? m1 : m2;
  130. }
  131.  
  132. int Segment_Tree::find_spot(char* start_number)
  133. {
  134.  
  135.     int start = stoi(start_number);
  136.     int min_num = get_min(0, start, this->count_numbers - 1);
  137.  
  138.     if (min_num == MAX)
  139.     {
  140.         min_num = get_min(0, 0, start - 1);
  141.  
  142.         if (min_num == MAX)
  143.             return -1;
  144.         else
  145.         {
  146.             set(min_num - 1, MAX);
  147.             return min_num;
  148.         }
  149.     }
  150.  
  151.     else
  152.     {
  153.         set(min_num - 1, MAX);
  154.         return min_num;
  155.     }
  156. }
  157.  
  158. int Segment_Tree::free_up(char* number)
  159. {
  160.     int num = stoi(number);
  161.  
  162.     if (tree[num - 1].res == MAX)
  163.     {
  164.         set(num - 1, num);
  165.         return 0;
  166.     }
  167.     else
  168.         return -2;
  169. }
  170.  
  171. void Segment_Tree::print_tree()
  172. {
  173.     int k = 2;
  174.     cout << "\ni= " << 0 << " (" << tree[0].left << ";" << tree[0].right << "): " << tree[0].res << endl;
  175.     for (int i=1; i < this->tree_size; ++i)
  176.     {
  177.         if (i == 2*k-1)
  178.         {
  179.             k *= 2;
  180.             cout << endl;
  181.         }
  182.         cout << "i= " << i << " (" << tree[i].left << ";" << tree[i].right << "): " << tree[i].res << "; ";
  183.     }
  184.     cout << endl;
  185. }
  186.  
  187. int main()
  188. {
  189.  
  190.     //int n, m;
  191.     //cin >> n >> m;
  192.  
  193.     Segment_Tree tree;
  194.     tree.Initialize(7);
  195.     //tree.print_tree();
  196.    
  197.  
  198.     cout << tree.get_min(0, 0, 6) << endl;
  199.     tree.set(0, 5);
  200.     cout << tree.get_min(0, 0, 6) << endl;
  201.     tree.set(6, 1);
  202.     tree.print_tree();
  203.     cout << tree.get_min(0, 0, 8) << endl;
  204.  
  205.  
  206. /*
  207.     string s;
  208.     for (int i = 0; i < m; ++i)
  209.     {
  210.         cin >> s;
  211.         char c = s[3];
  212.         if (s[0] == '+')
  213.             tree.find_spot(&c);
  214.         else
  215.             tree.free_up(&c);
  216.     }
  217. */
  218.     return 0;
  219. }
  220.  
RAW Paste Data