#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
struct node{
int mn,mx;
node(int mnn=-inf,int mxx=inf){
mn=mnn;
mx=mxx;
}
};
node seg[(1<<22)];
node lz[(1<<22)];
void add(int i,int k){
seg[i].mn=max(seg[i].mn,k);
seg[i].mx=max(seg[i].mx,k);
lz[i].mn=max(lz[i].mn,k);
lz[i].mx=max(lz[i].mx,k);
}
void rem(int i,int k){
seg[i].mn=min(seg[i].mn,k);
seg[i].mx=min(seg[i].mx,k);
lz[i].mn=min(lz[i].mn,k);
lz[i].mx=min(lz[i].mx,k);
}
void push(int i){
if(lz[i].mn!=-inf){
add(2*i,lz[i].mn);
add(2*i+1,lz[i].mn);
}
if(lz[i].mx!=inf){
rem(2*i,lz[i].mx);
rem(2*i+1,lz[i].mx);
}
lz[i]=node();
}
void upd(int l,int r,int i,int x,int y,int v,int op){
if(l>y||r<x)
return;
if(l>=x&&r<=y){
if(op==1)
add(i,v);
else
rem(i,v);
return;
}
push(i);
int m=(l+r)/2;
upd(l,m,2*i,x,y,v,op);
upd(m+1,r,2*i+1,x,y,v,op);
seg[i].mn=min(seg[2*i].mn,seg[2*i+1].mn);
seg[i].mx=max(seg[2*i+1].mx,seg[2*i+1].mx);
}
int qr(int l,int r,int i,int x){
if(l==r)
return seg[i].mn;
int m=(l+r)/2;
push(i);
if(x<=m)
return qr(l,m,2*i,x);
else
return qr(m+1,r,2*i+1,x);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=0;i<(1<<22);i++)
seg[i]=node(0,0);
for(int i=0;i<k;i++)
upd(0,n-1,1,left[i],right[i],height[i],op[i]);
for(int i=0;i<n;i++)
finalHeight[i]=qr(0,n-1,1,i);
return;
}
