#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int maxn = 2e6 + 10;
struct SegTree {
int maxx[4*maxn], minn[4*maxn], lz[4*maxn];
void init() {
for (int i = 0; i < maxn; ++i)
lz[i] = -1;
}
void unlazy(int node, int tl, int tr) {
if(lz[node] == -1) return;
maxx[node] = lz[node];
minn[node] = lz[node];
if(tl != tr) {
lz[2*node] = lz[node];
lz[2*node+1] = lz[node];
}
lz[node] = -1;
}
void update(int node, int l, int r, int tl, int tr, int val, int add) {
unlazy(node, tl, tr);
if(tl > r || tr < l) return;
if (tl >= l && tr <= r) {
if (add == 1) {
if (minn[node] >= val) return;
if (maxx[node] <= val) {
lz[node] = val;
unlazy(node, tl, tr);
return;
}
}
if (add == 2) {
if (maxx[node] <= val) return;
if (minn[node] >= val) {
lz[node] = val;
unlazy(node, tl, tr);
return;
}
}
}
int mid = (tl+tr)/2;
update(2*node, l, r, tl, mid, val, add);
update(2*node+1, l, r, mid+1, tr, val, add);
maxx[node] = max(maxx[2*node], maxx[2*node+1]);
minn[node] = min(minn[2*node], minn[2*node+1]);
}
int query(int node, int l, int r, int pos) {
unlazy(node,l,r);
if(l == r) return maxx[node];
int mid = (l+r)/2;
if(pos <= mid) return query(2*node, l, mid, pos);
return query(2*node+1, mid+1, r, pos);
}
} seg;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
seg.init();
for (int i = 0; i < k; ++i)
seg.update(1,left[i], right[i], 0, n-1, height[i], op[i]);
for (int i = 0; i < n; ++i)
finalHeight[i] = seg.query(1,0,n-1,i);
return;
}
