#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
int const MAX=2e6+5;
int const INF=1e9;
struct node{
int l,r;
void intersect(node ot){
if(r<ot.l)
*this={ot.l,ot.l};
else
if(ot.r<l)
*this={ot.r,ot.r};
else
*this={max(l,ot.l),min(r,ot.r)};
}
};
struct AINT{
node v[4*MAX];
void init(int nod,int st,int dr){
v[nod]={-INF,INF};
if(st<dr){
int mij=(st+dr)/2;
init(2*nod,st,mij);
init(2*nod+1,mij+1,dr);
}
}
void propagate(int nod){
v[2*nod].intersect(v[nod]);
v[2*nod+1].intersect(v[nod]);
v[nod]={-INF,INF};
}
void add(int nod,int st,int dr,int a,int b,int l,int r){
if(a<=st && dr<=b)
v[nod].intersect({l,r});
else{
propagate(nod);
int mij=(st+dr)/2;
if(a<=mij)
add(2*nod,st,mij,a,b,l,r);
if(b>mij)
add(2*nod+1,mij+1,dr,a,b,l,r);
}
}
void final_push(int nod,int st,int dr,int finalHeight[]){
if(st==dr)
finalHeight[st]=((v[nod].l>0)?v[nod].l:0);
else{
propagate(nod);
int mij=(st+dr)/2;
final_push(2*nod,st,mij,finalHeight);
final_push(2*nod+1,mij+1,dr,finalHeight);
}
}
}aint;
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
aint.init(1,0,n-1);
int i;
for(i=0;i<k;++i){
if(op[i]==1)
aint.add(1,0,n-1,left[i],right[i],height[i],INF);
else
aint.add(1,0,n-1,left[i],right[i],-INF,height[i]);
}
aint.final_push(1,0,n-1,finalHeight);
}
