#include "wall.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,pao=b;i<pao;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int MAXN=2e6;
struct Nodo{
int mini=0,maxi=INT_MAX;
Nodo():mini(0),maxi(INT_MAX){};
Nodo(int a, int b){
mini=a,maxi=b;
}
};
int N;
Nodo st[MAXN*4];
void apply(int x,Nodo h){
st[x].mini=max(st[x].mini,h.mini);
st[x].maxi=max(st[x].maxi,st[x].mini);
st[x].maxi=min(st[x].maxi,h.maxi);
st[x].mini=min(st[x].mini,st[x].maxi);
}
void push(int v){
apply(v*2,st[v]);
apply(v*2+1,st[v]);
st[v]=Nodo();
}
void upd(int ts,int te,Nodo h,int v=1,int s=0,int e=N-1){
if(e<ts||te<s)return;
if(ts<=s&&e<=te){
apply(v,h);
return;
}else{
push(v);
int m=(s+e)/2;
upd(ts,te,h,v*2,s,m);
upd(ts,te,h,v*2+1,m+1,e);
}
}
int que(int k,int v=1,int s=0,int e=N-1){
if(s==k&&e==k){
return st[v].mini;
}
push(v);
int m=(s+e)/2;
if(k<=m){
return que(k,v*2,s,m);
}else return que(k,v*2+1,m+1,e);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
N=n;
fore(i,0,k){
if(op[i]==1){
upd(left[i],right[i],Nodo(height[i],INT_MAX));
}else{
upd(left[i],right[i],Nodo(0,height[i]));
}
}
fore(i,0,n)finalHeight[i]=que(i);
return;
}
