#include "wall.h"
#include "bits/stdc++.h"
using namespace std;
const int N=100001;
const int INF=INT_MAX;
int h[N];
struct Fmx{
int st[N*4];
int lazy[N*4];
void push(int idx,int l,int r){
st[idx]=max(st[idx],lazy[idx]);
if(l!=r){
lazy[idx*2]=max(lazy[idx*2],lazy[idx]);
lazy[idx*2+1]=max(lazy[idx*2+1],lazy[idx]);
}
lazy[idx]=0;
}
void upd(int idx,int l,int r,int ql,int qr,int val){
push(idx,l,r);
if(ql>r||l>qr) return;
else if(ql<=l&&r<=qr){
lazy[idx]=max(lazy[idx],val);
push(idx,l,r);
return;
}
int mid=(l+r)>>1;
upd(2*idx,l,mid,ql,qr,val);
upd(2*idx+1,mid+1,r,ql,qr,val);
st[idx]=max(st[idx*2],st[idx*2+1]);
}
int ask(int idx,int l,int r,int ql,int qr){
push(idx,l,r);
if(ql>r||l>qr) return 0;
else if(ql<=l&&r<=qr) return st[idx];
int mid=(l+r)>>1;
return max(ask(2*idx,l,mid,ql,qr),ask(2*idx+1,mid+1,r,ql,qr));
}
};
Fmx fmx;
struct Fmn{
int st[N*4];
int lazy[N*4];
void init(){
for(int i=0;i<N*4;i++) lazy[i]=INF;
}
void build(int idx,int l,int r){
if(l==r){
st[idx]=h[l];
return;
}
int mid=(l+r)>>1;
build(2*idx,l,mid);
build(2*idx+1,mid+1,r);
st[idx]=min(st[idx*2],st[idx*2+1]);
}
void push(int idx,int l,int r){
st[idx]=min(st[idx],lazy[idx]);
if(l!=r){
lazy[idx*2]=min(lazy[idx*2],lazy[idx]);
lazy[idx*2+1]=min(lazy[idx*2+1],lazy[idx]);
}
lazy[idx]=INF;
}
void upd(int idx,int l,int r,int ql,int qr,int val){
if(ql>r||l>qr) return;
else if(ql<=l&&r<=qr){
lazy[idx]=min(lazy[idx],val);
return;
}
int mid=(l+r)>>1;
upd(2*idx,l,mid,ql,qr,val);
upd(2*idx+1,mid+1,r,ql,qr,val);
st[idx]=min(st[idx*2],st[idx*2+1]);
}
int ask(int idx,int l,int r,int ql,int qr){
push(idx,l,r);
if(ql>r||l>qr) return INF;
else if(ql<=l&&r<=qr) return st[idx];
int mid=(l+r)>>1;
return min(ask(2*idx,l,mid,ql,qr),ask(2*idx+1,mid+1,r,ql,qr));
}
};
Fmn fmn;
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
for(int i=0;i<k;i++){
if(op[i]==1) fmx.upd(1,1,n,left[i]+1,right[i]+1,height[i]);
}
for(int i=0;i<n;i++) finalHeight[i]=fmx.ask(1,1,n,i+1,i+1);
for(int i=1;i<=n;i++) h[i]=finalHeight[i-1];
fmn.init();
fmn.build(1,1,n);
for(int i=0;i<k;i++){
if(op[i]==2) fmn.upd(1,1,n,left[i]+1,right[i]+1,height[i]);
}
for(int i=0;i<n;i++) finalHeight[i]=fmn.ask(1,1,n,i+1,i+1);
return;
}
