#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
using ll = long long;
#define MAXN (1000005)
struct node{
int s,e,m,v,lazyaddatleast,lazyaddatmost;
node *l,*r;
node(int _s,int _e){
s = _s;
e = _e;
m = (s + e) / 2;
v = 0;
lazyaddatleast = 0;
lazyaddatmost = 0;
if(s != e){
l = new node(s,m);
r = new node(m + 1,e);
}
}
int value(){
if(s == e){
v = max(v,lazyaddatleast);
v = min(v,lazyaddatmost);
return v;
}
v = max(v,lazyaddatleast);
v = min(v,lazyaddatmost);
r->lazyaddatleast = max(lazyaddatleast,r->lazyaddatleast);
r->lazyaddatmost = min(lazyaddatmost,r->lazyaddatmost);
l->lazyaddatleast = max(lazyaddatleast,l->lazyaddatleast);
l->lazyaddatmost = min(lazyaddatmost,l->lazyaddatmost);
if(l->lazyaddatmost < l->lazyaddatleast){ //keep lazyaddatmost always larger than lazyaddatleast
l->lazyaddatmost = 1000000; //INF , but must also fufil lazyadd
}
if(r->lazyaddatmost < r->lazyaddatleast){ //keep lazyaddatmost always larger than lazyaddatleast
r->lazyaddatmost = 1000000; //INF
}
return v;
}
void atleast(int x,int y,int val){
if(s == x && e == y){
lazyaddatleast = val;
if(lazyaddatmost < lazyaddatleast){ //keep lazyaddmost always larger than lazyaddleast
lazyaddatmost = 1000000; //INF
}
}else{
if(x > m) r -> atleast(x,y,val);
else if(y <= m) l -> atleast(x,y,val);
else l -> atleast(x,m,val), r -> atleast(m + 1,y,val);
v = l->value() + r->value();
}
}
void atmost(int x,int y,int val){
if(s == x && e == y){
lazyaddatmost = val;
if(lazyaddatmost < lazyaddatleast){ //keep lazyaddmost always larger than lazyaddleast
lazyaddatleast = 0;
}
}else{
if(x > m) r -> atmost(x,y,val);
else if(y <= m) l -> atmost(x,y,val);
else l -> atmost(x,m,val), r -> atmost(m + 1,y,val);
v = l->value() + r->value();
}
}
int query(int x,int y){
value();
if(s == x && e == y) return value();
if(x > m) return r -> query(x,y);
if(y <= m) return l -> query(x,y);
return l -> query(x,m) + r -> query(m + 1,y);
}
} *root;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
root = new node(0,n + 5);
for(ll i = 0;i < k;i++){
if(op[i] == 1){
root->atleast(left[i] - 1,right[i] - 1,height[i]);
}else if(op[i] == 2){
root->atmost(left[i] - 1,right[i] - 1,height[i]);
}
}
for(ll i = 0;i < n;i++){
ll a = root->query(i,i);
finalHeight[i] = a;
}
return;
}
