#include "wall.h"
#include "bits/stdc++.h"
using namespace std;
const int N=100001;
const int INF=INT_MAX;
struct Node1{
int mn,mx;
};
struct Node2{
int add,rmv;
};
Node1 st[N*4];
Node2 lazy[N*4];
void push(int idx,int l,int r){
if(lazy[idx].rmv!=INF){
st[idx].mn=min(st[idx].mn,lazy[idx].rmv);
st[idx].mx=min(st[idx].mx,lazy[idx].rmv);
if(l!=r){
lazy[idx*2].rmv=min(lazy[idx*2].rmv,lazy[idx].rmv);
lazy[idx*2+1].rmv=min(lazy[idx*2+1].rmv,lazy[idx].rmv);
}
lazy[idx].rmv=INF;
}
if(lazy[idx].add!=-INF){
st[idx].mn=max(st[idx].mn,lazy[idx].add);
st[idx].mx=max(st[idx].mx,lazy[idx].add);
if(l!=r){
lazy[idx*2].add=max(lazy[idx*2].add,lazy[idx].add);
lazy[idx*2+1].add=max(lazy[idx*2+1].add,lazy[idx].add);
}
lazy[idx].add=-INF;
}
st[idx].mn=min(st[idx].mn,st[idx].mx);
}
void upd(int idx,int l,int r,int ql,int qr,int val,int tp){
push(idx,l,r);
if(ql>r||l>qr) return;
else if(ql<=l&&r<=qr){
if(tp==1) lazy[idx].add=max(lazy[idx].add,val);
if(tp==2) lazy[idx].rmv=min(lazy[idx].rmv,val);
push(idx,l,r);
return;
}
int mid=(l+r)>>1;
upd(2*idx,l,mid,ql,qr,val,tp);
upd(2*idx+1,mid+1,r,ql,qr,val,tp);
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 ql,int qr){
push(idx,l,r);
if(ql>r||l>qr) return -INF;
else if(ql<=l&&r<=qr) return st[idx].mx;
int mid=(l+r)>>1;
return max(ask(2*idx,l,mid,ql,qr),ask(2*idx+1,mid+1,r,ql,qr));
}
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=st[i].mn=0;
lazy[i].add=-INF;
lazy[i].rmv=INF;
}
for(int i=0;i<k;i++) upd(1,1,n,left[i]+1,right[i]+1,height[i],op[i]);
for(int i=0;i<n;i++) finalHeight[i]=ask(1,1,n,i+1,i+1);
return;
}
