#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
class SegTree{
public:
int left_index;
int right_index;
int lo_value;
int hi_value;
int lo_update;
int hi_update;
SegTree* left_child;
SegTree* right_child;
SegTree(int l, int r)
{
left_index = l;
right_index = r;
lo_value = 0;
hi_value = 0;
lo_update = -1;
hi_update = 999999;
if (l==r)
{
left_child = nullptr;
right_child = nullptr;
}
else
{
int m = (l+r)/2;
left_child = new SegTree(l, m);
right_child = new SegTree(m+1, r);
}
}
void push()
{
if (hi_value < lo_update)
{
lo_value = lo_update;
hi_value = lo_update;
}
else if (lo_value > hi_update)
{
lo_value = hi_update;
hi_value = hi_update;
}
else
{
lo_value = max(lo_value, lo_update);
hi_value = min(hi_value, hi_update);
}
if (left_child!=nullptr)
{
if (left_child->hi_update < lo_update)
{
left_child->lo_update = lo_update;
left_child->hi_update = lo_update;
}
else if (left_child->lo_update > hi_update)
{
left_child->lo_update = hi_update;
left_child->hi_update = hi_update;
}
else
{
left_child->lo_update = max(left_child->lo_update, lo_update);
left_child->hi_update = min(left_child->hi_update, hi_update);
}
if (right_child->hi_update < lo_update)
{
right_child->lo_update = lo_update;
right_child->hi_update = lo_update;
}
else if (right_child->lo_update > hi_update)
{
right_child->lo_update = hi_update;
right_child->hi_update = hi_update;
}
else
{
right_child->lo_update = max(right_child->lo_update, lo_update);
right_child->hi_update = min(right_child->hi_update, hi_update);
}
}
lo_update = -1;
hi_update = 999999;
}
void pull()
{
if (left_child != nullptr)
{
lo_value = min(left_child->lo_value, right_child->lo_value);
hi_value = max(left_child->hi_value, right_child->hi_value);
}
}
void modify_self(int typ, int h)
{
if (typ==1)
{
lo_update = h;
if (hi_update < h)
hi_update = h;
}
else
{
hi_update = h;
if (lo_update > h)
lo_update = h;
}
}
void builder(int typ, int l, int r, int h)
{
//cout << "nakarating sa " << left_index << right_index << l << r << '\n';
push();
int mid_index = (left_index+right_index)/2;
if ((l==left_index) and (r==right_index))
{
//grab_new_info();
modify_self(typ, h);
//update_children();
//grab_new_info();
//cout << "range is " << l << r << '\n';
}
else
{
push();
if (l<=mid_index)
left_child->builder(typ, l, min(mid_index, r), h);
if (r>=(mid_index+1))
right_child->builder(typ, max(l, mid_index+1), r, h);
pull();
}
}
void answer(int finalHeight[])
{
push();
if (left_index == right_index)
{
finalHeight[left_index] = lo_value;
}
else
{
left_child->answer(finalHeight);
right_child->answer(finalHeight);
}
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
SegTree* seg = new SegTree(0, n-1);
//cout << "nagawa\n";
for (int oper = 0; oper<k; oper++)
{
int typ = op[oper];
int l = left[oper];
int r = right[oper];
int h = height[oper];
seg->builder(typ, l, r, h);
//cout << "operation " << oper << " complete\n";
}
seg->answer(finalHeight);
}
