#include "wall.h"
struct Node {
Node(int start, int end, int value) {
this->start = start;
this->end = end;
this->value = value;
}
int start, end;
int value;
Node* left = nullptr;
Node* right = nullptr;
};
inline int max(int a, int b) {
if (a > b) {
return a;
}
return b;
}
inline int min(int a, int b) {
if (a < b) {
return a;
}
return b;
}
void updateAdd (int start, int end, int value, Node* node) {
if (start == node->start && end == node->end && node->left == nullptr && node->right == nullptr) {
node->value = max(node->value, value);
return;
}
int middle = (node->start + node->end) / 2;
if (start <= middle) { // insert on the left
if (node->left == nullptr) {
node->left = new Node(node->start, middle, node->value);
node ->right = new Node(middle+1, node->end, node->value);
}
updateAdd(start, min(middle, end), value, node->left);
}
if (end > middle) {
if (node->right == nullptr) {
node->left = new Node(node->start, middle, node->value);
node ->right = new Node(middle+1, node->end, node->value);
}
updateAdd(max(middle+1, start), end, value, node->right);
}
}
void updateRemove (int start, int end, int value, Node* node) {
if (start == node->start && end == node->end && node->left == nullptr && node->right == nullptr) {
node->value = min(node->value, value);
return;
}
int middle = (node->start + node->end) / 2;
if (start <= middle) { // insert on the left
if (node->left == nullptr) {
node->left = new Node(node->start, middle, node->value);
node ->right = new Node(middle+1, node->end, node->value);
}
updateRemove(start, min(middle, end), value, node->left);
}
if (end > middle) {
if (node->right == nullptr) {
node->left = new Node(node->start, middle, node->value);
node ->right = new Node(middle+1, node->end, node->value);
}
updateRemove(max(middle+1, start), end, value, node->right);
}
}
void PrintAll(Node* node, int finalHeight[]) {
if (node->left == nullptr && node->right == nullptr) {
for (int i = node->start; i <= node->end; i++) {
finalHeight[i] = node->value;
}
return;
}
if (node->left != nullptr) {
PrintAll(node->left, finalHeight);
}
if (node->right != nullptr) {
PrintAll(node->right, finalHeight);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
Node tree(0, n-1, 0);
for (int i=0; i<k; i++) {
if (op[i] == 1) {
updateAdd(left[i], right[i], height[i], &tree);
} else {
updateRemove(left[i], right[i], height[i], &tree);
}
}
PrintAll(&tree, finalHeight);
}
