Algorithms-2019/tree_heap.cpp at master · BMehron/Algorithms-2019 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <algorithm>
#include <iostream>
#include <memory>
#include <random>
#include <utility>
#include <vector>

using std::cin;
using std::cout;
using std::vector;

std::uniform_int_distribution<int> dist(0, 1e9);
std::random_device rd;
std::mt19937 gen(rd());

struct Node {
  int key_;
  long long priority_;
  int subtree_size_;
  std::shared_ptr<Node> left_child_;
  std::shared_ptr<Node> right_child_;

  explicit Node(int key) {
    key_ = key;
    priority_ = 1000000000 * static_cast<long long>(dist(gen)) + static_cast<long long>(dist(gen));
    subtree_size_ = 1;
    right_child_ = nullptr;
    left_child_ = nullptr;
  }
};

int GetSize(std::shared_ptr<Node> root) {
  return !root ? 0 : root->subtree_size_;
}

void UpdateSize(std::shared_ptr<Node> root) {
  if (root) {
    root->subtree_size_ = 1 + GetSize(root->left_child_) + GetSize(root->right_child_);
  }
}

int KthElement(std::shared_ptr<Node> root, int k_value) {
  if (!root || root->subtree_size_ < k_value)
    return -1;
  if (k_value <= GetSize(root->left_child_))
    return KthElement(root->left_child_, k_value);
  if (k_value == GetSize(root->left_child_) + 1)
    return root->key_;
  return KthElement(root->right_child_, k_value - GetSize(root->left_child_) - 1);
}

std::pair<std::shared_ptr<Node>, std::shared_ptr<Node>> Split(std::shared_ptr<Node> root, int key) {
  if (!root)
    return {nullptr, nullptr};
  if (key <= root->key_) {
    auto res = Split(root->left_child_, key);
    root->left_child_ = res.second;
    UpdateSize(root);
    return {res.first, root};
  } else {
    auto res = Split(root->right_child_, key);
    root->right_child_ = res.first;
    UpdateSize(root);
    return {root, res.second};
  }
}

std::shared_ptr<Node> Merge(std::shared_ptr<Node> LeftRoot, std::shared_ptr<Node> RightRoot) {
  if (!LeftRoot)
    return RightRoot;
  if (!RightRoot)
    return LeftRoot;
  if (LeftRoot->priority_ > RightRoot->priority_) {
    LeftRoot->right_child_ = Merge(LeftRoot->right_child_, RightRoot);
    UpdateSize(LeftRoot);
    return LeftRoot;
  } else {
    RightRoot->left_child_ = Merge(LeftRoot, RightRoot->left_child_);
    UpdateSize(RightRoot);
    return RightRoot;
  }
}

std::shared_ptr<Node> Insert(std::shared_ptr<Node> root, int val) {
  auto res = Split(root, val);
  auto new_node = std::make_shared<Node>(val);
  return Merge(Merge(res.first, new_node), res.second);
}

std::shared_ptr<Node> Erase(std::shared_ptr<Node> root, int val) {
  if (!root) {
    return nullptr;
  }
  if (root->key_ == val) {
    root = Merge(root->left_child_, root->right_child_);
  } else {
    if (root->key_ < val) {
      root->right_child_ = Erase(root->right_child_, val);
    } else {
      root->left_child_ = Erase(root->left_child_, val);
    }
  }
  UpdateSize(root);
  return root;
}

int main() {
  int arr_size, num_of_requests, k_value;
  cin >> arr_size >> num_of_requests >> k_value;
  vector<int> arr(arr_size);
  for (auto &elem : arr) {
    cin >> elem;
  }
  char sym;
  int left = 0, right = 0;
  auto root = std::make_shared<Node>(arr[0]);
  while (num_of_requests--) {
    cin >> sym;
    if (sym == 'R') {
      ++right;
      root = Insert(root, arr[right]);
    } else {
      root = Erase(root, arr[left]);
      ++left;
    }
    cout << KthElement(root, k_value) << '\n';
  }
  return 0;
}