#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 ui, bool add, int v)
{
if(l>ui||r<=ui) return;
if(l+1==r) {
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;
}
update(2*i,l,(l+r)/2,ui,add,v);
update(2*i+1,(l+r)/2,r,ui,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)
{
for(int i = left[ck]; i <= right[ck]; i++) update(1,0,n,i,op[ck]==1,height[ck]);
}
rep(i,n) finalHeight[i] = T[query(1,0,n,i)].minn;
}
