#include "wall.h"
struct node {
int lo,hi;
int lazylo,lazyhi;
bool haslazy;
node():lo(0),hi(1e9),lazylo(0),lazyhi(1e9),haslazy(false) {}
};
node seg[8000000];
int clamp (int v,int lo,int hi) {
if (v<lo) return lo;
if (v>hi) return hi;
return v;
}
void update(int idx,int l,int r,int ll,int rr,int op,int val) {
if (ll>=r||rr<=l) return;
//expand lazy
if (seg[idx].haslazy) {
if (l+1!=r) {
seg[idx*2+1].lazylo=clamp(seg[idx*2+1].lazylo,seg[idx].lazylo,seg[idx].lazyhi);
seg[idx*2+1].lazyhi=clamp(seg[idx*2+1].lazyhi,seg[idx].lazylo,seg[idx].lazyhi);
seg[idx*2+1].haslazy=true;
seg[idx*2+2].lazylo=clamp(seg[idx*2+2].lazylo,seg[idx].lazylo,seg[idx].lazyhi);
seg[idx*2+2].lazyhi=clamp(seg[idx*2+2].lazyhi,seg[idx].lazylo,seg[idx].lazyhi);
seg[idx*2+2].haslazy=true;
}
seg[idx].lo=clamp(seg[idx].lo,seg[idx].lazylo,seg[idx].lazyhi);
seg[idx].hi=clamp(seg[idx].hi,seg[idx].lazylo,seg[idx].lazyhi);
seg[idx].lazylo=0;
seg[idx].lazyhi=1e9;
seg[idx].haslazy=false;
}
//update
if (ll<=l&&rr>=r) {
if (op==1) {
//adjust lo
seg[idx].lazylo=clamp(seg[idx].lazylo,val,1e9);
seg[idx].lazyhi=clamp(seg[idx].lazyhi,val,1e9);
} else {
//adjust hi
seg[idx].lazyhi=clamp(seg[idx].lazyhi,0,val);
seg[idx].lazylo=clamp(seg[idx].lazylo,0,val);
}
seg[idx].haslazy=true;
return;
}
int m=(l+r)>>1;
update(idx*2+1,l,m,ll,rr,op,val);
update(idx*2+2,m,r,ll,rr,op,val);
}
int ans[2000100];
void getans(int idx,int l,int r) {
if (seg[idx].haslazy) {
if (l+1!=r) {
seg[idx*2+1].lazylo=clamp(seg[idx*2+1].lazylo,seg[idx].lazylo,seg[idx].lazyhi);
seg[idx*2+1].lazyhi=clamp(seg[idx*2+1].lazyhi,seg[idx].lazylo,seg[idx].lazyhi);
seg[idx*2+1].haslazy=true;
seg[idx*2+2].lazylo=clamp(seg[idx*2+2].lazylo,seg[idx].lazylo,seg[idx].lazyhi);
seg[idx*2+2].lazyhi=clamp(seg[idx*2+2].lazyhi,seg[idx].lazylo,seg[idx].lazyhi);
seg[idx*2+2].haslazy=true;
}
seg[idx].lo=clamp(seg[idx].lo,seg[idx].lazylo,seg[idx].lazyhi);
seg[idx].hi=clamp(seg[idx].hi,seg[idx].lazylo,seg[idx].lazyhi);
seg[idx].lazylo=0;
seg[idx].lazyhi=1e9;
seg[idx].haslazy=false;
}
if (l+1==r) {
ans[l]=seg[idx].lo;
return;
}
int m=(l+r)>>1;
getans(idx*2+1,l,m);
getans(idx*2+2,m,r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i=0;i<k;i++) {
update(0,0,n,left[i],right[i]+1,op[i],height[i]);
}
getans(0,0,n);
for (int i=0;i<n;i++){
finalHeight[i]=ans[i];
}
}
