#include "wall.h"
#include<bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
const int maxn=2e6+10;
pii seg[4*maxn]; //xx je max(ai,k), yy je min(ai,k)
int n;
pii comb(pii a,pii b){
if(a==mp(-1,-1)) return b;
if(b==mp(-1,-1)) return a;
pii ret=mp(min(a.xx,b.xx),max(a.yy,b.yy));
if(ret.xx<ret.yy){
if(ret.xx==a.xx) ret.yy=a.xx;
else ret.xx=a.yy;
}
return ret;
}
void push(int ind){
seg[2*ind]=comb(seg[ind],seg[2*ind]);
seg[2*ind+1]=comb(seg[ind],seg[2*ind+1]);
seg[ind]=mp(-1,-1);
}
void update(int tl,int tr,int hg,int hd,int ind=1,int l=0,int r=n-1){
if(l!=r) push(ind);
if(tl<=l && r<=tr){
seg[ind]=comb(mp(hg,hd),seg[ind]);
return;
}
int mid=l+(r-l)/2;
if(tl<=mid) update(tl,tr,hg,hd,2*ind,l,mid);
if(tr>mid) update(tl,tr,hg,hd,2*ind+1,mid+1,r);
}
int query(int t,int ind=1,int l=0,int r=n-1){
if(l!=r) push(ind);
if(l==r){
return seg[ind].xx;
}
int mid=l+(r-l)/2;
if(t<=mid) return query(t,2*ind,l,mid);
if(t>mid) return query(t,2*ind+1,mid+1,r);
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
n=N;
for(int i=0;i<k;i++){
if(op[i]==1){
update(left[i],right[i],INT_MAX,height[i]);
}else{
update(left[i],right[i],height[i],INT_MIN);
}
}
for(int i=0;i<n;i++) finalHeight[i]=query(i);
return;
}
