#include "wall.h"
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
using namespace std;
struct s
{
int minn = 0, maxx=1e15;
};
vector<s>T;
s def = s();
// s1 is new
int query(int i, int l, int r, int qi)
{
if(l>qi||r<=qi) return -1;
if(l+1==r) return i;
return max(query(2*i,l,(l+r)/2,qi), query(2*i+1,(l+r)/2,r,qi));
}
void update(int i, int l, int r, int ul, int ur, bool add, int v)
{
if(l>=ur||r<=ul) return;
if(l>=ul&&r<=ur) {
if(add) {
T[i].minn=max(T[i].minn,v);
T[i].maxx=max(T[i].maxx, v);
}
else { // cut down
T[i].maxx=min(T[i].maxx, v);
T[i].minn=min(T[i].minn,v);
}
return;
}
if(T[i].minn!=def.minn||T[i].maxx!=def.maxx)
{
rep(j,2)
{
T[2*i+j].minn=max(T[2*i+j].minn,T[i].minn);
T[2*i+j].maxx=max(T[2*i+j].maxx,T[i].minn);
T[2*i+j].maxx=min(T[2*i+j].maxx,T[i].maxx);
T[2*i+j].minn=min(T[2*i+j].minn,T[i].maxx);
}
T[i]=def;
}
update(2*i,l,(l+r)/2,ul,ur,add,v);
update(2*i+1,(l+r)/2,r,ul,ur,add,v);
}
void buildWall(signed n, signed k, signed op[], signed left[], signed right[], signed height[], signed finalHeight[]){
T.assign(4*n+2,s());
rep(ck,k)
{
update(1,0,n,left[ck],right[ck]+1,op[ck]==1,height[ck]);
}
rep(i,n) update(1,0,n,i,i+1,true,0);
rep(i,n) finalHeight[i] = T[query(1,0,n,i)].minn;
}
