#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define SZ(v) ((int)(v).size())
using ll = long long;
const int MAXN = 8e6;
int li[MAXN], ri[MAXN];
int lazyMin[MAXN], lazyMax[MAXN];
int val[MAXN];
void buildTree(int node, int l, int r)
{
li[node] = l, ri[node] = r;
lazyMin[node] = 1e9;
lazyMax[node] = 0;
if (l == r)
return ;
buildTree(2*node+1, l, (l+r)/2);
buildTree(2*node+2, (l+r)/2+1, r);
}
void changeMax(int node, int v)
{
lazyMax[node] = max(lazyMax[node], v);
lazyMin[node] = max(lazyMin[node], v);
}
void changeMin(int node, int v)
{
lazyMin[node] = min(lazyMin[node], v);
lazyMax[node] = min(lazyMax[node], v);
}
void push(int node)
{
if (li[node] == ri[node])
val[li[node]] = min(lazyMin[node], max(lazyMax[node], val[li[node]]));
else
{
changeMax(2*node+1, lazyMax[node]);
changeMin(2*node+1, lazyMin[node]);
changeMin(2*node+2, lazyMin[node]);
changeMax(2*node+2, lazyMax[node]);
}
lazyMin[node] = 1e9;
lazyMax[node] = 0;
}
void updateMax(int node, int lo, int up, int v)
{
push(node);
if (li[node] > up or ri[node] < lo)
return ;
if (li[node] >= lo and ri[node] <= up)
{
changeMax(node, v);
return;
}
updateMax(2*node+1, lo, up, v);
updateMax(2*node+2, lo, up, v);
}
void updateMin(int node, int lo, int up, int v)
{
push(node);
if (li[node] > up or ri[node] < lo)
return ;
if (li[node] >= lo and ri[node] <= up)
{
changeMin(node, v);
return;
}
updateMin(2*node+1, lo, up, v);
updateMin(2*node+2, lo, up, v);
}
void recursivePush(int node)
{
push(node);
if (li[node] < ri[node])
{
recursivePush(2*node+1);
recursivePush(2*node+2);
}
}
void buildWall(int n, int k, int op[], int l[], int r[], int v[], int fh[])
{
buildTree(0, 0, n-1);
for (int i(0); i < k; ++i)
{
if (op[i] == 1)
updateMax(0, l[i], r[i], v[i]);
else
updateMin(0, l[i], r[i], v[i]);
}
recursivePush(0);
for (int i(0); i < n; ++i)
fh[i] = val[i];
}
/*
int main(void)
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int nbCol, nbRequetes;
cin >> nbCol >> nbRequetes;
buildTree(0, 0, nbCol-1);
while (nbRequetes--)
{
int t, l, r, v;
cin >> t >> l >> r >> v;
if (t == 1)
updateMax(0, l, r, v);
else
updateMin(0, l, r, v);
}
recursivePush(0);
for (int i(0); i < nbCol; ++i)
cout << val[i] << '\n';
}*/
