#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
struct SegTree{
struct node{
int mini1,mini2;
int maxi1,maxi2;
node():mini1(0),mini2(INF),maxi1(0),maxi2(-INF){}
void setmax(int x){
if(x <= mini1)
return;
mini1 = x;
if(maxi1 <= x){
maxi1 = x;
maxi2 = -INF;
mini2 = INF;
}
else if(maxi2 < x){
maxi2 = x;
}
}
void setmin(int x){
if(x >= maxi1)
return;
maxi1 = x;
if(mini1 >= x){
mini1 = x;
maxi2 = -INF;
mini2 = INF;
}
else if(mini2 > x){
mini2 = x;
}
}
};
node merge(node a,node b){
if(a.maxi1 == b.maxi1){
a.maxi2 = max(a.maxi2,b.maxi2);
}
else{
if(a.maxi1 > b.maxi1){
a.maxi2 = max(a.maxi2,b.maxi1);
}
else{
a.maxi2 = max(a.maxi1,b.maxi2);
a.maxi1 = b.maxi1;
}
}
if(a.mini1 == b.mini1){
a.mini2 = min(a.mini2,b.mini2);
}
else{
if(a.mini1 < b.mini1){
a.mini2 = min(a.mini2,b.mini1);
}
else{
a.mini2 = min(a.mini1,b.mini2);
a.mini1 = b.mini1;
}
}
return a;
}
vector<node> t;
int n;
SegTree(int sz){
n = sz;
t.assign(4*n,node());
}
void push(int v){
t[v*2].setmax(t[v].mini1);
t[v*2].setmin(t[v].maxi1);
t[v*2 + 1].setmax(t[v].mini1);
t[v*2 + 1].setmin(t[v].maxi1);
}
void upd(int v,int tl,int tr,int l,int r,int val,int op){
if(tr < l || r < tl || (op == 1 && t[v].mini1 >= val) || (op == 2 && t[v].maxi1 <= val)){
return;
}
if(l <= tl && tr <= r && ((op == 1 && t[v].mini2 > val) || (op == 2 && t[v].maxi2 < val))){
if(op == 1){
t[v].setmax(val);
}
else t[v].setmin(val);
return;
}
push(v);
int tm = (tl + tr)/2;
upd(v*2,tl,tm,l,r,val,op);
upd(v*2 + 1,tm+1,tr,l,r,val,op);
t[v] = merge(t[v*2],t[v*2+1]);
}
int get(int v,int tl,int tr,int pos){
if(tl == tr){
return t[v].maxi1;
}
push(v);
int tm = (tl + tr)/2;
if(pos <= tm){
return get(v*2,tl,tm,pos);
}
return get(v*2+1,tm+1,tr,pos);
}
void upd(int l,int r,int val,int op){
upd(1,0,n-1,l,r,val,op);
}
int get(int pos){
return get(1,0,n-1,pos);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
SegTree t(n);
for(int i = 0;i<k;i++){
t.upd(left[i],right[i],height[i],op[i]);
}
for(int i = 0;i<n;i++){
finalHeight[i] = t.get(i);
}
}
