#include "wall.h"
#include<bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
struct SegTree{
int N;
const int INF=1e9;
vector<int>mn,mx;
SegTree(int n){
N=1;
while(N<n) N<<=1;
mn.assign(2*N,INF);
mx.assign(2*N,0);
}
void impact(int v,int x,int id){
if(id&1){
mx[v]=max(mx[v],x);
if(mn[v]<x){
if(v<N){
impact(v<<1,mn[v],2);
impact(v<<1|1,mn[v],2);
}
mn[v]=INF;
}
}
else{
mn[v]=min(mn[v],x);
if(mx[v]>mn[v]) mx[v]=mn[v];
}
}
void push(int v){
if(mx[v]!=0){
impact(v<<1,mx[v],1);
impact(v<<1|1,mx[v],1);
mx[v]=0;
}
if(mn[v]!=INF){
impact(v<<1,mn[v],2);
impact(v<<1|1,mn[v],2);
mn[v]=INF;
}
}
void update(int v,int l,int r,int ql,int qr,int x,int id,int c){
if(ql>=r || l>=qr) return;
if(l>=ql && qr>=r){
impact(v,x,id);
return;
}
push(v);
int mid=(l+r)/2;
update(v<<1,l,mid,ql,qr,x,id,c);
update(v<<1|1,mid,r,ql,qr,x,id,c);
}
void update(int l,int r,int x,int id,int c){
return update(1,0,N,l,r,x,id,c);
}
int get(int v,int l,int r,int id){
if(r-l==1){
return min(mn[v],mx[v]);
}
push(v);
// cout<<tree[v]<<' ';
int mid=(l+r)/2;
if(mid>id) return get(v<<1,l,mid,id);
return get(v<<1|1,mid,r,id);
}
int get(int id){
return get(1,0,N,id);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
SegTree S(n);
for(int i=0;i<k;i++){
S.update(left[i],right[i]+1,height[i],op[i],i);
}
for(int i=0;i<n;i++){
finalHeight[i]=S.get(i);
// cout<<'\n';
}
return;
}
