#include "wall.h"
#pragma once
#include <algorithm>
#include <cstdio>
using namespace std;
const int NMAX = 2e6;
pair<int,int> aint[4 * NMAX + 5];
void prop(pair<int,int> &a,pair<int,int> &b){
if(a.second < b.first){
b = {a.second,a.second};
}
else if(b.second < a.first){
b = {a.first,a.first};
}
else{
b = {max(a.first,b.first),min(a.second,b.second)};
}
}
void propag(int nod,int st,int dr){
if(st == dr){
return ;
}
prop(aint[nod],aint[nod * 2]);
prop(aint[nod],aint[nod * 2 + 1]);
aint[nod] = {0,1e5};
}
void build(int nod,int st,int dr){
aint[nod] = {0,1e5};
if(st == dr){
return ;
}
int mid = (st + dr) / 2;
build(nod * 2,st,mid);
build(nod * 2 + 1,mid + 1,dr);
}
void update(int nod,int st,int dr,int op,int l,int r,int h){
propag(nod,st,dr);
if(dr < l || st > r){
return ;
}
if(l <= st && dr <= r){
pair<int,int> tmp = {0,1e5};
if(op == 1){
tmp.first = h;
}
else{
tmp.second = h;
}
prop(tmp,aint[nod]);
return ;
}
int mid = (st + dr) / 2;
update(nod * 2,st,mid,op,l,r,h);
update(nod * 2 + 1,mid + 1,dr,op,l,r,h);
}
void dfs(int nod,int st,int dr,int ans[]){
propag(nod,st,dr);
if(st == dr){
ans[st - 1] = aint[nod].first;
return ;
}
int mid = (st + dr) / 2;
dfs(nod * 2,st,mid,ans);
dfs(nod * 2 + 1,mid + 1,dr,ans);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
build(1,1,n);
for(int i = 0;i < k;i++){
update(1,1,n,op[i],left[i] + 1,right[i] + 1,height[i]);
}
dfs(1,1,n,finalHeight);
}
