#include "wall.h"
#include "bits/stdc++.h"
using namespace std;
const int maxn = 2000005;
int N, K;
int mn[maxn << 2], mx[maxn << 2], t[maxn << 2];
void applymn(int node, int h){
mn[node] = min(mn[node], h);
mx[node] = min(mx[node], mn[node]);
}
void applymx(int node, int h){
mx[node] = max(mx[node], h);
mn[node] = max(mn[node], mx[node]);
}
void push_down(int node){
applymn(2*node, mn[node]);
applymn(2*node + 1, mn[node]);
applymx(2*node, mx[node]);
applymx(2*node + 1, mx[node]);
mn[node] = INT_MAX;
mx[node] = 0;
}
void upd(int node, int b, int e, int i, int j, int val, int id){
if(i > e || j < b)return;
if(b >= i && j >= e){
if(id == 1){
applymx(node, val);
}else {
applymn(node, val);
}
return;
}
push_down(node);
int mid = (b + e) >> 1;
upd(2*node, b, mid, i, j, val, id);
upd(2*node + 1, mid + 1, e, i, j, val, id);
}
int query(int node, int b, int e, int i){
if(b == e){
return min(max(0, mn[node]), mx[node]);
}else {
push_down(node);
int mid = (b + e) >> 1;
if(i <= mid){
return query(2*node, b, mid, i);
}else {
return query(2*node + 1, mid + 1, e, i);
}
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
N = n, K = k;
for(int i = 0; i < (maxn << 2); ++i){
mn[i] = INT_MAX;
mx[i] = 0;
}
for(int i = 0; i < K; ++i){
upd(1, 1, N, left[i] + 1, right[i] + 1, height[i], op[i]);
}
for(int i = 1; i <= N; ++i){
finalHeight[i - 1] = query(1, 1, N, i);
}
return;
}
