#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
struct node{
int s,e,m,omin,omax,flag;
node *l, *r;
node (int _s, int _e){
s = _s, e = _e, m = (s+e)/2;
omin = 100005, omax = 0, flag = 0;
if (s != e){
l = new node(s,m);
r = new node(m+1,e);
}
}
void value(){
//printf("\t\tvalue %d %d %d %d %d\n",i,s,e,omin,omax);
if (s != e){
//printf("%d %d , ",s,e);
l->mini(s,m,omin);
l->maxi(s,m,omax);
r->mini(m+1,e,omin);
r->maxi(m+1,e,omax);
omax = 0, omin = 100005;
}
}
int mini(int qs, int qe, int x){
if (qs == s && qe == e){
//printf("range match %d %d, applying first\n",qs,qe);
omin = min(omin,x);
omax = min(omax,omin);
}
else{
// printf("min %d %d %d %d %d\n",qs,qe,s,e,x);
value();
//printf("%d %d %d %d\n",qs,qe,s,e);
if (qe <= m) l->mini(qs,qe,x);
else if (qs > m) r->mini(qs,qe,x);
else{
l->mini(qs,m,x);
r->mini(m+1,qe,x);
}
}
}
int maxi(int qs, int qe, int x){
if (qs == s && qe == e){
//printf("range match %d %d, applying first\n",qs,qe);
omax = max(x,omax);
omin = max(omax,omin);
}
else{
//printf("max %d %d %d %d %d\n",qs,qe,s,e,x);
value();
//printf("%d %d %d %d\n",qs,qe,s,e);
if (qe <= m) l->maxi(qs,qe,x);
else if (qs > m) r->maxi(qs,qe,x);
else{
l->maxi(qs,m,x);
r->maxi(m+1,qe,x);
}
}
}
int qu(int x){
value();
//printf("query %d %d %d\n",s,e,x);
if (s == e){
//printf("qu %d %d %d\n",s,omin,omax);
return omax;
}
if (x <= m){
return l->qu(x);
}
else return r->qu(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 (int i = 0; i < k; i++){
//printf("\t\t\t%d update %d %d %d %d\n",i,op[i],left[i],right[i],height[i]);
if (op[i] == 1){
root->maxi(left[i],right[i],height[i]);
}
else{
root ->mini(left[i],right[i],height[i]);
}
}
//printf("updates over %d %d\n",ooo,oo);
for (int i =0; i < n; i++){
finalHeight[i] = root->qu(i);
}
return;
}
