#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
using ll = int;
#define MAXN (1000005)
struct node {
node *l, *r;
ll s,e,m,opmax,opmin;
node(ll _s,ll _e){
s=_s,e=_e,m=(s+e)/2;
opmax = opmin = 0;
if(s!=e)l=new node(s,m),r=new node(m+1,e);
}
void minimise(ll x,ll y,ll nval){
value();
if(s==x&&e==y) {
if(opmax > nval) {
opmax = nval;
if(opmin > nval)opmin=nval;
}
return;
}
if(x>m)r->minimise(x,y,nval);
else if(y<=m)l->minimise(x,y,nval);
else l->minimise(x,m,nval),r->minimise(m+1,y,nval);
opmax = max(l->opmax, r->opmax);
opmin = min(l->opmin, r->opmin);
}
void maximise(ll x,ll y,ll nval){
value();
if(s==x&&e==y) {
if(opmin < nval) {
opmin = nval;
if(opmax < nval)opmax=nval;
}
return;
}
if(x>m)r->maximise(x,y,nval);
else if(y<=m)l->maximise(x,y,nval);
else l->maximise(x,m,nval),r->maximise(m+1,y,nval);
opmax = max(l->opmax, r->opmax);
opmin = min(l->opmin, r->opmin);
}
void value() {
if(s==e) return;
if(opmin > l->opmin || opmin > r->opmin) {
l->opmin=max(l->opmin, opmin);
r->opmin=max(r->opmin, opmin);
if(l->opmax < l->opmin) l->opmax = l->opmin;
if(r->opmax < r->opmin) r->opmax = r->opmin;
}
if(opmax < l->opmax || opmax < r->opmax) {
l->opmax=min(l->opmax, opmax);
r->opmax=min(r->opmax, opmax);
if(l->opmax < l->opmin) l->opmin = l->opmax;
if(r->opmax < r->opmin) r->opmin = r->opmax;
}
}
ll query(ll x){
value();
if(s==e) {
assert(opmin==opmax);
return opmin;
}
if(x>m)return r->query(x);
else return l->query(x);
}
} *root;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
root = new node(0,n - 1);
for(ll i = 0;i < k;i++){
if(op[i] == 1){
root -> maximise(left[i],right[i],height[i]);
}else if(op[i] == 2){
root -> minimise(left[i],right[i],height[i]);
}
}
for(ll i = 0;i < n;i++){
finalHeight[i] = root -> query(i);
}
return;
}
