#include "wall.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
int* pt;
struct segtree {
int n, ptwo;
struct Node {
// Change here the values you want to propagate, and store
int mn =0, mx = 100000;
int l,r;
Node () {}
Node(int i) {
l = r = i;
}
};
vector<Node> d;
void set(int i, int mn, int mx) {
Node& rc = d[i];
rc.mn = max(mn,rc.mn);
rc.mx = min(mx,rc.mx);
if(rc.mn>rc.mx) {
if(mn>rc.mx) rc.mx = rc.mn;
else rc.mn = rc.mx;
}
}
void push(int i) {
// Pushes the propagation values down to the children
set(2*i, d[i].mn, d[i].mx);
set(2*i+1, d[i].mn, d[i].mx);
d[i].mn = 0; d[i].mx = 100000;
}
segtree(int _n) {
n = _n;
ptwo= 1;
while(ptwo<n) ptwo*=2;
d.resize(2*ptwo);
for(int i=ptwo;i<ptwo*2;++i) {
d[i] = Node(i-ptwo);
}
for(int i=ptwo-1;i>0;--i) {
d[i].l = d[i*2].l; d[i].r = d[i*2+1].r;
}
}
void query(int i=1, int mn = 0, int mx = 100000) {
Node& c = d[i];
if(c.l>=n) return;
mn = max(mn,c.mn);
mx = min(mx,c.mx);
if(mn>mx) {
if(c.mn>mx) mn = mx;
else mx = mn;
}
if(c.l==c.r) {
*pt = mn;
pt++;
return;
}
query(i*2,mn,mx);
query(i*2+1,mn,mx);
}
void update(int l, int r, bool lower, int val, int i=1) {
Node& c = d[i];
if(c.l < l or r < c.r ) {
push(i);
int mid = (c.r+c.l)/2;
if(l<=mid) {
update(l,r,lower,val,i*2);
}
if(r>mid) {
update(l,r,lower,val,i*2+1);
}
} else {
if(!lower) {
c.mn = max(val,c.mn);
if(c.mn>c.mx) c.mx = c.mn;
} else {
c.mx = min(val,c.mx);
if(c.mn>c.mx) c.mn = c.mx;
}
}
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
segtree seg(n);
pt = finalHeight;
for(int i=0;i<k;++i) {
seg.update(left[i],right[i], op[i]==2, height[i]);
}
seg.query();
}
