#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
struct SegTree{
struct node{
int maxi,mini;
node():maxi(0),mini(0){}
};
vector<node> t;
int n;
SegTree(int sz){
n = sz;
t.assign(4*n,node());
}
void push(int v){
t[v*2].mini = max(t[v*2].mini,t[v].mini);
t[v*2].maxi = max(t[v*2].maxi,t[v*2].mini);
t[v*2].maxi = min(t[v*2].maxi,t[v].maxi);
t[v*2].mini = min(t[v*2].maxi,t[v*2].mini);
t[v*2 + 1].mini = max(t[v*2 + 1].mini,t[v].mini);
t[v*2 + 1].maxi = max(t[v*2 + 1].maxi,t[v*2 + 1].mini);
t[v*2 + 1].maxi = min(t[v*2 + 1].maxi,t[v].maxi);
t[v*2 + 1].mini = min(t[v*2 + 1].maxi,t[v*2 + 1].mini);
}
void upd(int v,int tl,int tr,int l,int r,int val,int op){
if(tr < l || r < tl){
return;
}
if(l <= tl && tr <= r){
//cout << tl << ' ' << tr << endl;
if(op == 1){
t[v].mini = max(t[v].mini,val);
t[v].maxi = max(t[v].maxi,t[v].mini);
}
else{
t[v].maxi = min(t[v].maxi,val);
t[v].mini = min(t[v].mini,t[v].maxi);
}
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].maxi = max(t[v*2].maxi,t[v*2+1].maxi);
t[v].mini = min(t[v*2].mini,t[v*2+1].mini);
}
int get(int v,int tl,int tr,int pos){
//cout << tl << ' ' << tr << ' ' << t[v].mini << ' ' << t[v].maxi << endl;
if(tl == tr){
return t[v].maxi;
}
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);
}
}
