#include "wall.h"
//#include <stdio.h>
struct Node
{
Node(int start, int end, int value)
{
this->start = start;
this->end = end;
this->value = value;
this->min_value = value;
this->max_value = value;
}
~Node()
{
if (left != nullptr)
{
delete left;
}
if (right != nullptr)
{
delete right;
}
}
void SetValueForRange(int value)
{
this->value = value;
this->min_value = value;
this->max_value = value;
if (left)
delete left;
left = nullptr;
if (right)
delete right;
right =nullptr;
}
int start, end;
int value;
int min_value, max_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 ) {
if (node->max_value <= value) {
node->SetValueForRange(value);
return;
}
if (node->min_value >= value) {
return;
}
}
int middle = (node->start + node->end) / 2;
if (node->left == nullptr) {
node->left = new Node(node->start, middle, node->value);
node->right = new Node(middle + 1, node->end, node->value);
}
if (start <= middle) {
updateAdd(start, min(middle, end), value, node->left);
}
if (end > middle) {
updateAdd(max(middle + 1, start), end, value, node->right);
}
node->min_value = min(node->left->min_value, node->right->min_value);
node->max_value = max(node->left->max_value, node->right->max_value);
}
void updateRemove(int start, int end, int value, Node *node) {
//printf("[%d, %d] = %d", start, end, value);
//printf("(%d %d %d %d %d %d)", node->start, node->end, node->min_value, node->max_value, node->left!=nullptr?1:0, node->right!=nullptr?1:0);
if (start == node->start && end == node->end ) {
if (node->min_value >= value) {
node->SetValueForRange(value);
return;
}
if (node->max_value <= value) {
return;
}
}
int middle = (node->start + node->end) / 2;
if (node->left == nullptr) {
node->left = new Node(node->start, middle, node->value);
node->right = new Node(middle + 1, node->end, node->value);
}
if (start <= middle) {
updateRemove(start, min(middle, end), value, node->left);
}
if (end > middle) {
updateRemove(max(middle + 1, start), end, value, node->right);
}
node->min_value = min(node->left->min_value, node->right->min_value);
node->max_value = max(node->left->max_value, node->right->max_value);
}
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);
}
