#include "wall.h"
#include<algorithm>
using namespace std;
const int MAX_N=2000000;
struct st{
int mini,maxi;
st():mini(0),maxi(0x7fffffff){}
}tree[MAX_N*4];
int *final;
void update(int now,int l,int r,int gl,int gr,int mini,int maxi){
if(r<gl||gr<l) return;
if(gl<=l&&r<=gr){
tree[now].mini=min(maxi,max(tree[now].mini,mini));
tree[now].maxi=max(mini,min(tree[now].maxi,maxi));
if(l==r) final[l]=tree[now].mini;
return;
}
int m=(l+r)/2;
update(now*2+1,l,m,l,m,tree[now].mini,tree[now].maxi);
update(now*2+2,m+1,r,m+1,r,tree[now].mini,tree[now].maxi);
tree[now].mini=0; tree[now].maxi=0x7fffffff;
update(now*2+1,l,m,gl,gr,mini,maxi);
update(now*2+2,m+1,r,gl,gr,mini,maxi);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
final=finalHeight;
for(int i=0; i<k; i++)
update(0,0,n-1,left[i],right[i],
op[i]==1?height[i]:0,op[i]==2?height[i]:0x7fffffff);
for(int i=0; i<n; i++)
update(0,0,n-1,i,i,0,0x7fffffff);
}
