#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxN = 2e6 + 5;
const int INF = 1e9 + 5;
struct Segtree{
struct Node{
int min_val;
int max_val;
Node(){
min_val = 0;
max_val = INF;
}
Node(int min_, int max_){
min_val = min_;
max_val = max_;
}
Node operator+(Node b){
Node res;
res.min_val = max(min_val, b.min_val);
res.max_val = max(res.min_val, max_val);
res.max_val = min(res.max_val, b.max_val);
res.min_val = min(res.max_val, res.min_val);
return res;
}
};
Node st[4*maxN], lazy[4*maxN];
void down(int id){
Node val = lazy[id];
st[id*2] = st[id*2] + val;
lazy[id*2] = lazy[id*2] + val;
st[id*2 + 1] = st[id*2 + 1] + val;
lazy[id*2 + 1] = lazy[id*2 + 1] + val;
lazy[id] = Node();
}
void update(int id, int l, int r, int u, int v, Node val){
if (l > v || r < u)
return;
if (l >= u && r <= v){
st[id] = st[id] + val;
lazy[id] = lazy[id] + val;
return;
}
down(id);
int mid = (l + r)/2;
update(id*2, l, mid, u, v, val);
update(id*2 + 1, mid+1, r, u, v, val);
st[id] = st[id*2] + st[id*2 + 1];
}
void update(int n, int l, int r, Node val){
update(1, 1, n, l, r, val);
}
Node get(int id, int l, int r, int u, int v){
if (l > v || r < u)
return Node();
if (l >= u && r <= v)
return st[id];
down(id);
int mid = (l + r)/2;
return get(id*2, l, mid, u, v) +
get(id*2 + 1, mid+1, r, u, v);
}
int get(int n, int l, int r){
return get(1, 1, n, l, r).min_val;
}
} seg;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i = 0; i < k; ++i){
if (op[i] == 1){
seg.update(n, left[i] + 1, right[i] + 1, Segtree::Node(height[i], INF));
}
else{
seg.update(n, left[i] + 1, right[i] + 1, Segtree::Node(0, height[i]));
}
}
for (int i = 0; i < n; ++i){
finalHeight[i] = seg.get(n, i+1, i+1);
}
return;
}
