#include <bits/stdc++.h>
#include "wall.h"
#define N 2000001
using namespace std;
int seg[4 * N][2]; // 2 parts for add and remove ops
void update(int s, int e, int l, int r, int i, int cur, bool op){
cur = max(cur, seg[i][0]); cur = min(cur, seg[i][1]);
if(l > s || e < r) return;
if(l >= s || e <= r){
if(!op) seg[i][0] = cur; else seg[i][1] = cur;
return;
}
update(s, e, l, (l + r) / 2, 2 * i, cur, op); update(s, e, (l + r) / 2 + 1, e, 2 * i + 1, cur, op);
}
void build(int l, int r, int i, int cur, int* ans){
cur = max(cur, seg[i][0]); cur = min(cur, seg[i][1]);
if(l == r) ans[l] = cur;
build(l, (l + r) / 2, 2 * i, cur, ans);
build((l + r) / 2 + 1, r, 2 * i + 1, cur, ans);
}
void buildWall(int n, int k, int* op, int* l, int* r, int* h, int* ans){
for(int i = 0; i < 4 * n; i++){seg[i][0] = 0; seg[i][1] = INT_MAX;}
for(int i = k - 1; i > -1; i--) update(l[i], r[i], 0, n - 1, 1, h[i], op[i] - 1);
build(0, n - 1, 1, 0, ans);
}
