#include "wall.h"
const int HMX = 100001;
inline int _min(int a, int b){ return a<b ? a : b; }
inline int _max(int a, int b){ return a>b ? a : b; }
struct node {
int up=0, dn=0;
node(){}
node(int a, int b): up(a), dn(b) {}
node operator + (const node& nd) const {
node res = *this;
res.up = _max(res.up, nd.up);
res.dn = _max(res.dn, nd.up);
res.dn = _min(res.dn, nd.dn);
return res;
}
} T[1<<22];
void busy(int v, int s, int e){
if(s==e) return;
node &ndl = T[v*2], &ndr = T[v*2+1], &nd = T[v];
ndl = ndl + nd, ndr = ndr + nd;
nd.up = 0, nd.dn = HMX;
}
void upt(int v, int s, int e, int l, int r, int op, int h){
if(l<=s && e<=r){
T[v] = T[v] + node(op==1 ? h : 0, op==2 ? h : HMX); return;
}
busy(v,s,e);
int m = (s+e)/2;
if(l<=m) upt(v*2,s,m,l,r,op,h);
if(m<r) upt(v*2+1,m+1,e,l,r,op,h);
}
void get(int v, int s, int e, int ans[]){
busy(v,s,e);
if(s==e){ ans[s] = _min(_max(0, T[v].up), T[v].dn); return; }
get(v*2, s, (s+e)/2, ans);
get(v*2+1, (s+e)/2+1, e, ans);
}
void buildWall(int n, int k, int op[], int L[], int R[], int H[], int ans[]){
for(int i=0; i<k; i++) upt(1, 0, n-1, L[i], R[i], op[i], H[i]);
get(1,0,n-1,ans);
return;
}
