#include <bits/stdc++.h>
#include "wall.h"
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
int N, K, blocksz;
vector<int>ans, ans2;
vector<int>values;
struct segTree
{
int dd, ht, minimum, maximum, mid;
segTree *L, *R;
segTree(int l, int r){
dd = l, ht = r;
mid = (l+r)/2;
minimum = 0, maximum = 1000000000;
if(l!=r){
L=new segTree(l, mid);
R=new segTree(mid+1, r);
}
}
void lazy(){
L->operate(dd, mid, 1, minimum);
L->operate(dd, mid, 2, maximum);
R->operate(mid+1, ht, 1, minimum);
R->operate(mid+1, ht, 2, maximum);
minimum = 0;
maximum = 1000000000;
}
void operate(int l, int r, int op, int val){
if(l == dd && r == ht){
if(op==1){
if(minimum < val){
minimum = val;
if(maximum < minimum)maximum = minimum;
}
}else{
if(maximum > val){
maximum = val;
if(minimum > maximum)minimum = maximum;
}
}
}else{
lazy();
if(r<= mid){
L->operate(l, r, op, val);
}else if(l > mid){
R->operate(l, r, op, val);
}else{
L->operate(l, mid, op, val);
R->operate(mid+1, r, op, val);
}
}
}
void answ(){
if(dd!=ht){
lazy();
L->answ();
R->answ();
}else{
ans.pb(minimum);
}
}
};
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 < n ; i ++){
values.pb(0);
}
segTree *st = new segTree(0, n-1);
for(int i = 0 ; i < k ; ++i){
st->operate(left[i], right[i], op[i], height[i]);
}
st->answ();
for(int i = 0 ; i < n ; i ++)finalHeight[i] = ans[i];
return;
}
