#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
int N;
vector<pair<int,int>> lazy;
void merge(int node, pair<int,int> p){
if (p.second >= lazy[node].first && lazy[node].second >= p.first){
lazy[node].first = max(lazy[node].first, p.first);
lazy[node].second = min(lazy[node].second, p.second);
return;
}
if (p.first > lazy[node].second) lazy[node] = {p.first, p.first};
else lazy[node] = {p.second, p.second};
return;
}
void prop(int node){
merge(node*2, lazy[node]);
merge(node*2+1, lazy[node]);
lazy[node] = {0, 100000};
return;
}
void update(int l, int r, pair<int,int> p, int node=1, int tl=0, int tr=N-1){
if (l <= tl && tr <= r){
merge(node, p);
return;
}
prop(node);
int tm = (tl+tr)/2;
if (l <= tm) update(l, r, p, node*2, tl, tm);
if (tm+1 <= r) update(l, r, p, node*2+1, tm+1, tr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
N = n;
lazy.resize(4*n, {0, 100000});
for (int i=0; i<k; i++){
if (op[i] == 1) update(left[i], right[i], {height[i], 100000});
else update(left[i], right[i], {0, height[i]});
}
for (int i=0; i<n; i++){
finalHeight[i] = 0;
int cur = 1, tl = 0, tr = n-1;
while (tl != tr){
int tm = (tl+tr)/2;
if (i <= tm){
cur = cur*2;
tr = tm;
}
else {
cur = cur*2+1;
tl = tm+1;
}
}
while (cur){
if (finalHeight[i] < lazy[cur].first) finalHeight[i] = lazy[cur].first;
if (finalHeight[i] > lazy[cur].second) finalHeight[i] = lazy[cur].second;
cur >>= 1;
}
}
return;
}
