#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define P push
typedef long long ll;
const int maxn=2000000;
ll mini[maxn*4];
ll maxi[maxn*4];
ll finh[maxn];
void update_seg(ll c,ll l,ll h){
if(maxi[c]<=l)mini[c]=maxi[c]=l;
else if(mini[c]>=h)mini[c]=maxi[c]=h;
else{
maxi[c]=min(maxi[c],h);
mini[c]=max(mini[c],l);
}
}
void update(ll a,ll b,ll c,ll l,ll h,ll x,ll y){
if(a==x && b==y){
update_seg(c,l,h);
return;
}
update_seg(2*c,mini[c],maxi[c]);
update_seg(2*c+1,mini[c],maxi[c]);
mini[c]=0;maxi[c]=INT32_MAX;
ll m=(a+b)/2;
if(y<=m)update(a,m,2*c,l,h,x,y);
else if(x>m)update(m+1,b,2*c+1,l,h,x,y);
else{
update(a,m,2*c,l,h,x,m);
update(m+1,b,2*c+1,l,h,m+1,y);
}
}
void finalize(ll a,ll b,ll c){
if(a==b){finh[a]=mini[c];return;}
ll m=(a+b)/2;
update_seg(2*c,mini[c],maxi[c]);
update_seg(2*c+1,mini[c],maxi[c]);
finalize(a,m,2*c);
finalize(m+1,b,2*c+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=0;i<k;i++){
if(op[i]==1)update(0,n-1,1,height[i],INT32_MAX,left[i],right[i]);
else update(0,n-1,1,0,height[i],left[i],right[i]);
}
finalize(0,n-1,1);
for(int i=0;i<n;i++)finalHeight[i]=finh[i];
return;
}
