#include "wall.h"
#include <bits/stdc++.h>
#define pb push_back
#define fr first
#define sc second
#define mk make_pair
using namespace std;
const int N = (int) 2e6 + 6;
int nn;
struct node {
int mn,mx;
node () {
mx = 0,mn = 1e6 + 5;
}
}t[N * 4];
void upd (int tp,int v,int h) {
if (tp == 1) {
t[v].mx = max(t[v].mx,h);
t[v].mn = max(t[v].mn,h);
}
else {
t[v].mn = min(t[v].mn,h);
t[v].mx = min(t[v].mx,h);
}
}
void push(int v) {
upd(1,v + v,t[v].mx);
upd(2,v + v,t[v].mn);
upd(1,v + v + 1,t[v].mx);
upd(2,v + v + 1,t[v].mn);
t[v].mx = 0,t[v].mn = 1e6 + 5;
}
void update (int tp,int l,int r,int h,int v = 1,int tl = 0,int tr = nn - 1) {
if (tl > r || tr < l) return ;
if (l <= tl && tr <= r)
upd(tp,v,h);
else {
push(v);
int tm = (tl + tr) >> 1;
update (tp,l,r,h,v + v,tl,tm);
update (tp,l,r,h,v + v + 1,tm + 1,tr);
}
}
void get(int finalHeight[],int v = 1,int tl = 0,int tr = nn - 1) {
if (tl == tr)
finalHeight[tl] = min(t[v].mx,t[v].mn);
else {
push(v);
int tm = (tl + tr) >> 1;
get(finalHeight,v + v,tl,tm);
get(finalHeight,v + v + 1,tm + 1,tr);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
nn = n;
for (int i = 0; i < k; i ++)
update (op[i],left[i],right[i],height[i]);
get(finalHeight);
}
