#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
#define all(x) x.begin(),x.end()
#define maxn 2000005
#define INF 1023456789
struct node{
int s,e,m,mn,mx,lzmn,lzmx;//value has to between [mn, mx];
node *l=NULL,*r=NULL;
node(int _s,int _e){
s=_s,e=_e,m=(s+e)>>1,mn=0,mx=INF,lzmn=0,lzmx=INF;
}
void create(){
if(l!=NULL)return;
l=new node(s,m);
r=new node(m+1,e);
l->mn=r->mn=mn;
l->mx=r->mx=mx;
}
ii join(ii l,ii r){
auto[lmn,lmx]=l;
auto[rmn,rmx]=r;
if(max(lmn,rmn)<=min(lmx,rmx))return {max(lmn,rmn),min(lmx,rmx)};
else if(rmx<=lmn)return {rmx,rmx};
else return {rmn,rmn};
}
void ppo(){
tie(mn,mx)=join({mn,mx},{lzmn,lzmx});
if(s!=e){
create();
tie(l->lzmn,l->lzmx)=join({l->lzmn,l->lzmx},{lzmn,lzmx});
tie(r->lzmn,r->lzmx)=join({r->lzmn,r->lzmx},{lzmn,lzmx});
}
lzmn=0,lzmx=INF;
}
void up(int x,int y,int type,int h){
if(s==x&&e==y){
if(type==1)tie(lzmn,lzmx)=join({lzmn,lzmx},{h,INF});
else tie(lzmn,lzmx)=join({lzmn,lzmx},{0,h});
return;
}
create();ppo();
if(y<=m)l->up(x,y,type,h);
else if(x>m)r->up(x,y,type,h);
else{
l->up(x,m,type,h);
r->up(m+1,y,type,h);
}
l->ppo(),r->ppo();
tie(mn,mx)=join({l->mn,l->mx},{r->mn,r->mx});
}
ii qry(int x){
create();ppo();
if(s==x&&e==x)return {mn,mx};
if(x<=m)return l->qry(x);
else return r->qry(x);
}
}*rt;
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
rt=new node(0,n-1);
for(int i=0;i<k;++i){
rt->up(left[i],right[i],op[i],height[i]);
}
for(int i=0;i<n;++i){
finalHeight[i]=rt->qry(i).first;
}
}
