#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
vector<int> st;
vector<array<int, 2>> lazy;
void push(int l, int r, int x){
if(l == r){
st[x] = max(st[x], lazy[x][0]);
st[x] = min(st[x], lazy[x][1]);
lazy[x] = {-1, INT_MAX};
return;
}
lazy[2 * x + 1][0] = max(lazy[2 * x + 1][0], lazy[x][0]);
lazy[2 * x + 1][1] = min(lazy[2 * x + 1][1], lazy[x][1]);
lazy[2 * x + 2][0] = max(lazy[2 * x + 2][0], lazy[x][0]);
lazy[2 * x + 2][1] = min(lazy[2 * x + 2][1], lazy[x][1]);
lazy[x] = {-1, INT_MAX};
}
void update(int lq, int rq, int l, int r, int i, int to, int x){
push(l, r, x);
if(lq > r || l > rq) return;
if(lq <= l && r <= rq){
lazy[x][i] = to;
return;
}
int mid = (l + r) / 2;
update(lq, rq, l, mid, i, to, 2 * x + 1);
update(lq, rq, mid + 1, r, i, to, 2 * x + 2);
}
int query(int i, int l, int r, int x){
push(l, r, x);
if(l == r){
return st[x];
}
int mid = (l + r) / 2;
if(i <= mid) return query(i, l, mid, 2 * x + 1);
else return query(i, mid + 1, r, 2 * x + 2);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
st.resize(4 * n + 4, 0);
lazy.resize(4 * n + 4, {-1, INT_MAX});
for(int i = 0; i < k; i++){
update(left[i], right[i], 0, n, op[i] - 1, height[i], 0);
}
for(int i = 0; i < n; i++) finalHeight[i] = query(i, 0, n, 0);
}
