vadimk772336

начало дерева отрезок

Dec 7th, 2021
829
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <math>
  3. #include <string>
  4. using namespace std;
  5.  
  6. const MAX = 2e5;
  7.  
  8. class Segment_Tree
  9. {
  10.     int* tree;
  11.     int tree_size;
  12.     int count_numbers;
  13.     std::vector<int> numbers;
  14.  
  15. public:
  16.     segment_tree();
  17.     segment_tree(int count_numbers);
  18. };
  19.  
  20. void Segment_Tree::build_tree(const std::vector<int>& numbers, int v, int tl, int tr)
  21. {
  22.  
  23.     if (tr - tl == 1)
  24.         tree[v] = numbers[tl];
  25.     else
  26.     {
  27.         int tm = (tl + tr) / 2;
  28.         build (numbers, v*2+1, tl, tm);
  29.         build (numbers, v*2+2, tm, tr);
  30.         tree[v] = tree[v*2+1] + tree[v*2+2];
  31.     }
  32.  
  33. }
  34.  
  35. int Segment_Tree::to_deg_of_two(std::vector<int>& numbers, int count_numbers)
  36. {
  37.    
  38.     int p = 1;
  39.     while (count_numbers > p)
  40.         p *= 2;
  41.        
  42.     for (int i =0; i < p-count_numbers; ++i)
  43.         numbers.push_back(MAX);
  44.    
  45.     return 2*p;
  46.        
  47. }
  48.    
  49. Segment_Tree::Initialize(int count_numbers)
  50. {
  51.  
  52.     this->count_numbers = count_numbers;
  53.     for (int i =1; i <= count_numbers; ++i)
  54.         numbers.push_back(i);
  55.    
  56.     this->tree_size = to_deg_of_two(numbers, count_numbers);
  57.     this->tree = new int[tree_size];
  58.     build_tree(numbers, 0, 0, count_numbers);
  59. }
  60.  
  61. Segment_Tree::get_min(int l, int r)
  62. {
  63.    
  64. }
  65.  
  66.  
  67. Segment_Tree::find_spot(char start_number)
  68. {
  69.     int start = stoi(start_number);
  70.     int min_num = get_min(start, this->count_numbers-1);
  71.    
  72.     if (min_num == MAX)
  73.     {
  74.         min_num = get_min(0, start-1);
  75.        
  76.         if (min_num == MAX)
  77.             return -1 :
  78.         else
  79.         {
  80.             set(min_num-1,MAX);
  81.             return min_num;
  82.         }
  83.     }
  84.    
  85.     else
  86.     {
  87.         set(min_num-1,MAX);
  88.         return min_num;
  89.     }
  90.    
  91. }
  92.  
  93. Segment_Tree::free_up(char number)
  94. {
  95.     int num = stoi(number);
  96.    
  97.     if tree[num-1] == MAX
  98.     {
  99.         set(num-1,num);
  100.         return 0;
  101.     }
  102.     else
  103.         return -2;
  104. }
  105.  
  106. int main()
  107. {
  108.    
  109.     int n,m;
  110.     cin >> n >> m;
  111.    
  112.     Segment_Tree tree;
  113.     tree.Initialize(n);
  114.    
  115.     string s[3];
  116.     for (int i=0; i < m; ++i)
  117.     {
  118.         cin >> s;
  119.         if (s[0] == "+")
  120.             find_spot(s[3]);
  121.         else    
  122.             free_up(s[3]);
  123.     }
  124.  
  125.     return 0;
  126. }
  127.  
RAW Paste Data