#include "wall.h"
# include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 2;
struct st{
int mx, mn, x, c, b, y;
st(){
mx = x = b = 0;
mn = y = 1e5 + 1;
}
}t[N * 4];
int n;
void push(int v, int tl, int tr){
if(t[v].b){
t[v].mx = max(t[v].mx, t[v].x);
if(tl != tr){
t[v << 1].b = t[(v << 1) | 1].b = 1;
t[v << 1].x = max(t[v << 1].x, t[v].x);
t[(v << 1) | 1].x = max(t[(v << 1) | 1].x, t[v].x);
}
t[v].b = 0;
}
if(t[v].c){
t[v].mn = min(t[v].mn, t[v].y);
if(tl != tr){
t[v << 1].c = t[(v << 1) | 1].c = 1;
t[v << 1].y = min(t[v << 1].y, t[v].y);
t[(v << 1) | 1].y = min(t[(v << 1) | 1].y, t[v].y);
}
t[v].c = 0;
}
}
void update(int l, int r, int x, int tp, int v = 1, int tl = 1, int tr = n){
push(v, tl, tr);
if(tl > r || l > tr) return ;
if(l <= tl && tr <= r){
if(tp == 1){
t[v].x = x;
t[v].b = 1;
} else {
t[v].y = x;
t[v].c = 1;
}
push(v, tl, tr);
return ;
}
int tm = (tl + tr) >> 1;
update(l, r, x, tp, v << 1, tl, tm);
update(l, r, x, tp, (v << 1) | 1, tm + 1, tr);
}
int get(int pos, int v = 1, int tl = 1, int tr = n){
push(v, tl, tr);
if(tl == tr){
return min(t[v].mn, t[v].mx);
}
int tm = (tl + tr) >> 1;
if(pos <= tm)
return get(pos, v << 1, tl, tm);
return get(pos, (v << 1) | 1, tm + 1, tr);
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
n = N;
if(n <= 10000 && k <= 5000){
for(int i = 0; i < k; i ++){
for(int j = left[i]; j <= right[i]; j ++){
if(op[i] == 1){
finalHeight[j] = max(finalHeight[j], height[i]);
} else {
finalHeight[j] = min(finalHeight[j], height[i]);
}
}
}
} else {
for(int i = 0; i < k; i ++){
update(left[i] + 1, right[i] + 1, height[i], op[i]);
}
for(int i = 0; i < n; i ++){
finalHeight[i] = get(i + 1);
}
}
}
