#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
const int inf=1000000100;
const int MAXN=2000010;
int A[MAXN];
pii seg[MAXN<<2];
pii Merge(pii a, pii b){
if (a.second<b.first) return {b.first, b.first};
if (b.second<a.first) return {b.second, b.second};
return {max(a.first, b.first), min(a.second, b.second)};
}
void shift(int id){
seg[id<<1]=Merge(seg[id<<1], seg[id]);
seg[id<<1 | 1]=Merge(seg[id<<1 | 1], seg[id]);
seg[id]=seg[0];
}
void Put(int id, int tl, int tr, int l, int r, pii p){
if (r<=tl || tr<=l) return ;
if (l<=tl && tr<=r){
seg[id]=Merge(seg[id], p);
// debugp(seg[id])
return ;
}
shift(id);
int mid=(tl+tr)>>1;
Put(id<<1, tl, mid, l, r, p);
Put(id<<1 | 1, mid, tr, l, r, p);
}
void dfs(int id, int tl, int tr){
if (tr-tl==1){
A[tl]=Merge({0, 0}, seg[id]).first;
return ;
}
shift(id);
int mid=(tl+tr)>>1;
dfs(id<<1, tl, mid);
dfs(id<<1 | 1, mid, tr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
fill(seg, seg+MAXN*4, pii(0, inf));
for (int i=0; i<k; i++){
int l=left[i], r=right[i]+1, h=height[i];
if (op[i]==1) Put(1, 0, n, l, r, {h, inf});
if (op[i]==2) Put(1, 0, n, l, r, {0, h});
}
dfs(1, 0, n);
for (int i=0; i<n; i++) finalHeight[i]=A[i];
return;
}
