#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
struct segS
{
pair<int, int> val= {0, 1e9};
bool lazy = false;
};
vector<segS> seg;
void calc(int p, pair<int, int> val)
{
if(val.first > seg[p].val.second)
seg[p].val = {val.first, val.first};
else if(val.second < seg[p].val.first)
seg[p].val = {val.second, val.second};
else
{
seg[p].val.first = max(seg[p].val.first, val.first);
seg[p].val.second = min(seg[p].val.second, val.second);
}
seg[p].lazy = true;
}
void push(int p)
{
if(!seg[p].lazy)
return;
calc(2*p, seg[p].val);
calc(2*p+1, seg[p].val);
seg[p].val = {0, 1e9};
seg[p].lazy=false;
}
void upd(int stt, int drt, int st, int dr, int p, pair<int, int> val)
{
if(stt == st && drt == dr)
{
calc(p, val);
return;
}
push(p);
int mij=(st+dr)/2;
if(drt <= mij)
upd(stt, drt, st, mij, 2*p, val);
else if(stt > mij)
upd(stt, drt, mij+1, dr, 2*p+1, val);
else
{
upd(stt, mij, st, mij, 2*p, val);
upd(mij+1, drt, mij+1, dr, 2*p+1, val);
}
}
void pushAll(int st, int dr, int p, int ans[])
{
if(st == dr)
{
ans[st] = seg[p].val.first;
return;
}
push(p);
int mij=(st+dr)/2;
pushAll(st, mij, 2*p, ans);
pushAll(mij+1, dr, 2*p+1, ans);
}
void afis(int st, int dr, int p)
{
cout<<st<<' '<<dr<<' '<<seg[p].val.first<<' '<<seg[p].val.second<<' '<<seg[p].lazy<<'\n';
if(st < dr)
{
int mij=(st+dr)/2;
afis(st, mij, 2*p);
afis(mij+1, dr, 2*p+1);
}
}
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[])
{
seg.resize(4*n + 4);
for(int i=0; i<k; i++)
{
if(op[i] == 1)
upd(l[i], r[i], 0, n-1, 1, {h[i], 1e9});
else
upd(l[i], r[i], 0, n-1, 1, {0, h[i]});
}
pushAll(0, n-1, 1, ans);
}
