#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e6;
struct Node {
int l = 0, r = INT_MAX;
Node() {}
Node(int x): l(x), r(x) {}
Node(int l, int r): l(l), r(r) {}
} st[4 * MAXN + 5];
int a[MAXN + 5];
Node intersect(Node a, Node b) {
if(max(a.l, b.l) <= min(a.r, b.r)) return Node(max(a.l, b.l), min(a.r, b.r));
else if(a.r < b.l) return Node(b.l);
else return Node(b.r);
}
void down(int id, int l, int r) {
if(l != r) {
st[id * 2] = intersect(st[id * 2], st[id]);
st[id * 2 + 1] = intersect(st[id * 2 + 1], st[id]);
st[id] = Node();
}
}
void upd(int id, int l, int r, int u, int v, Node x) {
down(id, l, r);
if(v < l || r < u) return;
if(u <= l && r <= v) {
st[id] = intersect(st[id], x);
down(id, l, r);
return;
}
int mid = (l + r) / 2;
upd(id * 2, l, mid, u, v, x);
upd(id * 2 + 1, mid + 1, r, u, v, x);
st[id] = Node();
}
void build(int id, int l, int r) {
down(id, l, r);
if(l == r) a[l] = st[id].l;
else {
int mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i = 0; i < k; i++) {
int t = op[i], l = left[i], r = right[i], h = height[i];
l++, r++;
upd(1, 1, n, l, r, (t == 1 ? Node(h, INT_MAX) : Node(0, h)));
}
build(1, 1, n);
for(int i = 1; i <= n; i++) finalHeight[i - 1] = a[i];
return;
}
