#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6+5;
const int INF = 1e9;
bool has_lazy[4*MAXN];
struct Node{
int mn,mx;
Node(){
mn = 0;
mx = INF;
}
};
Node lazy[4*MAXN];
void push(int v, int tl, int tr){
if (has_lazy[v]){
int tm = (tl+tr)/2;
lazy[2*v].mn = min(lazy[v].mx, max(lazy[v].mn, lazy[2*v].mn));
lazy[2*v].mx = min(lazy[v].mx, max(lazy[v].mn, lazy[2*v].mx));
lazy[2*v+1].mn = min(lazy[v].mx, max(lazy[v].mn, lazy[2*v+1].mn));
lazy[2*v+1].mx = min(lazy[v].mx, max(lazy[v].mn, lazy[2*v+1].mx));
has_lazy[v] = false;
lazy[v] = Node();
has_lazy[2*v] = true;
has_lazy[2*v+1] = true;
}
}
void update(int v, int tl, int tr, int l, int r, int constraint, bool type1){
if (l > r) return;
//type1 0 -> max
//type1 1 -> mn
if (!type1){
if (l == tl && r == tr){
lazy[v].mn = max(lazy[v].mn, constraint);
lazy[v].mx = max(lazy[v].mx, constraint);
has_lazy[v] = true;
}
else{
push(v, tl, tr);
int tm = (tl+tr)/2;
update(2*v, tl, tm, l, min(r,tm), constraint, type1);
update(2*v+1, tm+1, tr, max(l,tm+1), r, constraint, type1);
}
}
else{
if (l == tl && r == tr){
lazy[v].mn = min(lazy[v].mn, constraint);
lazy[v].mx = min(lazy[v].mx, constraint);
has_lazy[v] = true;
}
else{
push(v, tl, tr);
int tm = (tl+tr)/2;
update(2*v, tl, tm, l, min(r,tm), constraint, type1);
update(2*v+1, tm+1, tr, max(l,tm+1), r, constraint, type1);
}
}
}
void build_final(int v, int tl, int tr, int finalHeight[]){
if (tl == tr){
finalHeight[tl] = lazy[v].mn;
return;
}
push(v, tl, tr);
int tm = (tl+tr)/2;
build_final(2*v, tl, tm, finalHeight);
build_final(2*v+1, tm+1, tr, finalHeight);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i = 0; i<4*n; i++){
lazy[i] = Node();
has_lazy[i] = false;
}
for (int i = 0; i<k; i++){
bool type1 = (op[i] == 2);
update(1,0,n-1,left[i],right[i],height[i],type1);
}
build_final(1, 0, n-1, finalHeight);
return;
}
