#include "wall.h"
#include "bits/stdc++.h"
using namespace std;
const int N=100001;
struct Node{
int mx,mn;
};
Node st[N*4];
deque<pair<int,int>>lazy[N*4];
void push(int idx,int l,int r){
while(!lazy[idx].empty()){
pair<int,int>p=lazy[idx].front();
int tp=p.first;
int val=p.second;
if(tp==1){
st[idx].mx=max(st[idx].mx,val);
st[idx].mn=max(st[idx].mx,val);
}
else{
st[idx].mx=min(st[idx].mx,val);
st[idx].mn=min(st[idx].mx,val);
}
if(l!=r){
lazy[idx*2].push_back(p);
lazy[idx*2+1].push_back(p);
}
lazy[idx].pop_front();
}
}
void upd(int idx,int l,int r,int ql,int qr,int t,int val){
push(idx,l,r);
if(ql>r||l>qr) return;
if(ql<=l&&r<=qr){
lazy[idx].push_back({t,val});
push(idx,l,r);
return;
}
int mid=(l+r)>>1;
upd(2*idx,l,mid,ql,qr,t,val);
upd(2*idx+1,mid+1,r,ql,qr,t,val);
st[idx].mx=max(st[idx*2].mx,st[idx*2+1].mx);
st[idx].mn=min(st[idx*2].mn,st[idx*2+1].mn);
}
int ask(int idx,int l,int r,int pos){
push(idx,l,r);
if(l==r){
return st[idx].mx;
}
int mid=(l+r)>>1;
if(mid>=pos) ask(2*idx,l,mid,pos);
else ask(2*idx+1,mid+1,r,pos);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
for(int i=0;i<N*4;i++){
st[i].mx=0;
st[i].mn=0;
}
for(int i=0;i<k;i++){
if(op[i]==1) upd(1,1,n,left[i]+1,right[i]+1,op[i],height[i]);
}
for(int i=0;i<n;i++) finalHeight[i]=ask(1,1,n,i+1);
return;
}
