#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define vl vector<ll>
#define vb vector<bool>
#define pb push_back
#define ff(aa, bb, cc) for(ll aa = bb; aa < cc; aa++)
#define pll pair<ll, ll>
#define fi first
#define se second
#define ed "\n"
#define all(aaa) aaa.begin(), aaa.end()
#define rall(aaa) aaa.rbegin(), aaa.rend()
ll MOD = 1e9+7;
vector<pll> t;
vl val;
void propagar(ll cur, ll l, ll r){
if(l == r){
val[l] = max(val[l], t[cur].fi);
val[l] = min(val[l], t[cur].se);
t[cur] = {0, 1e9};
return;
}
ll i = 2*cur+1, j = 2*cur+2;
t[i].fi = max(t[i].fi, t[cur].fi);
t[i].se = max(t[i].fi, t[i].se);
t[i].se = min(t[i].se, t[cur].se);
t[i].fi = min(t[i].fi, t[i].se);
t[j].fi = max(t[j].fi, t[cur].fi);
t[j].se = max(t[j].se, t[j].fi);
t[j].se = min(t[j].se, t[cur].se);
t[j].fi = min(t[j].fi, t[j].se);
t[cur] = {0, 1e9};
}
void update(ll i, ll tl, ll tr, ll l, ll r, ll v, ll tt){
propagar(i, tl, tr);
if(tr < l || r < tl){
return;
}
if(l <= tl && tr <= r){
if(tt == 1){
t[i].fi = v;
}
else{
t[i].se = v;
}
return;
}
ll mid = (tl+tr)/2;
update(2*i+1, tl, mid, l, r, v, tt);
update(2*i+2, mid+1, tr, l, r, v, tt);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
t = vector<pll>(4*n, {0, 1e9});
val = vl(n, 0);
ff(i, 0, k){
update(0, 0, n-1, left[i], right[i], height[i], op[i]);
}
ff(i, 0, n){
update(0, 0, n-1, i, i, 0, 1);
}
ff(i, 0, n){
finalHeight[i] = val[i];
//cout << finalHeight[i];
}
}
/*
int main(){
ll n, k;
cin >> n >> k;
ll a[n], b[n], c[n], d[n];
ff(i, 0, k){
cin >> a[i] >> b[i] >> c[i] >> d[i];
}
ll x[n];
buildWall(n, k, a, b, c, d, x);
}
*/
