#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define pii pair<int,int>
const int base=1<<21;
pii tree[2*base];
void lazy_prop(int v){
if (v>=base)return;
if (tree[v].first>=tree[2*v].second)tree[2*v]={tree[v].first,tree[v].first};
else if (tree[v].second<=tree[2*v].first)tree[2*v]={tree[v].second,tree[v].second};
else{
tree[2*v].first=max(tree[2*v].first,tree[v].first);
tree[2*v].second=min(tree[2*v].second,tree[v].second);
}
if (tree[v].first>=tree[2*v+1].second)tree[2*v+1]={tree[v].first,tree[v].first};
else if (tree[v].second<=tree[2*v+1].first)tree[2*v+1]={tree[v].second,tree[v].second};
else{
tree[2*v+1].first=max(tree[2*v+1].first,tree[v].first);
tree[2*v+1].second=min(tree[2*v+1].second,tree[v].second);
}
}
void update(int v, int l, int p, int a, int b, pii op){
if (a<=l && p<=b){
if (op.first==1){
tree[v].first=max(tree[v].first,op.second);
tree[v].second=max(tree[v].second,tree[v].first);
}
else{
tree[v].second=min(tree[v].second,op.second);
tree[v].first=min(tree[v].second,tree[v].first);
}
lazy_prop(v);
return;
}
else if (p<a || b<l){
lazy_prop(v);
return;
}
else{
lazy_prop(v);
update(2*v,l,(l+p)/2,a,b,op);
update(2*v+1,(l+p)/2+1,p,a,b,op);
tree[v]={min(tree[2*v].first,tree[2*v+1].first),max(tree[2*v].second,tree[2*v+1].second)};
}
}
void finalProp(int v){
if (v>=base)return;
lazy_prop(v);
finalProp(2*v);
finalProp(2*v+1);
}
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]){
for (int i = 0; i<k; i++)update(1,0,base-1,left[i],right[i],{op[i],height[i]});
finalProp(1);
for (int i = 0; i<n; i++)finalHeight[i]=tree[base+i].first;
}
