#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
const int lim = 2e6 + 5;
const int INF = 2e9;
pair<int, int>st[lim << 2];
void solve(int id, int l, int r, int cur, int* ans){
maximize(cur, st[id].first);
minimize(cur, st[id].second);
if(l == r){
ans[l] = cur;
}
else{
int m = (l + r) >> 1;
solve(id << 1, l, m, cur, ans);
solve(id << 1 | 1, m + 1, r, cur, ans);
}
}
void update(int id, int l, int r, int cur, int u, int v, bool is_maximize){
if(l > v || r < u){
return;
}
maximize(cur, st[id].first);
minimize(cur, st[id].second);
if(u <= l && v >= r){
if(is_maximize){
st[id].first = cur;
}
else{
st[id].second = cur;
}
return;
}
int m = (l + r) >> 1;
update(id << 1, l, m, cur, u, v, is_maximize);
update(id << 1 | 1, m + 1, r, cur, u, v, is_maximize);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i = n << 2; i > 0; i--){
st[i] = make_pair(0, INF);
}
for(int i = k - 1; i > -1; i--){
update(1, 0, n - 1, height[i], left[i], right[i], op[i] == 1);
}
solve(1, 0, n - 1, 0, finalHeight);
}
