#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
const int N = 4e6 + 5, INF = 1000000007;
pair<int, int> seg[4 * N];
void build(int k, int l, int r)
{
if(l == r)
{
seg[k] = {0, INF};
return ;
}
int mid = (l + r) / 2;
build(2 * k, l, mid);
build(2 * k + 1, mid + 1, r);
seg[k] = {0, INF};
}
void f(int k, int l, int r, int flag, int val)
{
if(flag == 1)
{
if(val >= seg[k].second)
{
seg[k] = {val, val};
}
if(val >= seg[k].first)
{
seg[k].first = val;
}
}
if(flag == 0)
{
if(val <= seg[k].first)
{
seg[k] = {val, val};
}
if(val <= seg[k].second)
{
seg[k].second = val;
}
}
}
void push(int k, int l, int r)
{
int mid = (l + r) / 2;
if(seg[k].first != 0)
{
f(2 * k, l, mid, 1, seg[k].first);
f(2 * k + 1, mid + 1, r, 1, seg[k].first);
}
if(seg[k].second != INF)
{
f(2 * k, l, mid, 0, seg[k].second);
f(2 * k + 1, mid + 1, r, 0, seg[k].second);
}
seg[k] = {0, INF};
}
void update(int k, int l, int r, int upd_l, int upd_r, int flag, int val)
{
if(upd_r < l or r < upd_l)
{
return ;
}
if(upd_l <= l and r <= upd_r)
{
f(k, l, r, flag, val);
return ;
}
push(k, l, r);
int mid = (l + r) / 2;
update(2 * k, l, mid, upd_l, upd_r, flag, val);
update(2 * k + 1, mid + 1, r, upd_l, upd_r, flag, val);
}
int query(int k, int l, int r, int node)
{
if(l == r)
{
return seg[k].first;
}
int mid = (l + r) / 2;
push(k, l, r);
if(node <= mid)
return query(2 * k, l, mid, node);
else
return query(2 * k + 1, mid + 1, r, node);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
build(1, 1, n);
for(int i = 0; i < k; i++)
{
update(1, 1, n, left[i] + 1, right[i] + 1, 2 - op[i], height[i]);
}
for(int i = 1; i <= n; i++)
{
finalHeight[i - 1] = query(1, 1, n, i);
}
return;
}
