#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Lazy_Segtree {
#define left v + 1
#define right v + 2 * (tm - tl)
struct pi {
int l = 0, r = 1e9 + 99;
} emp;
vector<pi> tree;
void init (int x) {
tree.assign (x << 1, emp);
}
void built (int v, int tl, int tr, vector<int> &arr) {
if (tl + 1 == tr) {
tree[v].l = tree[v].r = arr[tl];
return;
}
int tm = (tl + tr) >> 1;
built(left, tl, tm, arr);
built(right, tm, tr, arr);
}
void push(int v, int tl, int tr) {
if (tl + 1 == tr) return;
int tm = (tl + tr) >> 1;
tree[left].l = max(tree[left].l, tree[v].l);
tree[left].r = max(tree[left].r, tree[left].l);
tree[left].r = min(tree[left].r, tree[v].r);
tree[left].l = min(tree[left].l, tree[left].r);
tree[right].l = max(tree[right].l, tree[v].l);
tree[right].r = max(tree[right].r, tree[right].l);
tree[right].r = min(tree[right].r, tree[v].r);
tree[right].l = min(tree[right].l, tree[right].r);
tree[v].l = 0;
tree[v].r = 1e9 + 99;
}
void update1 (int v, int tl, int tr, int ql, int qr, int val) {
if (ql >= tr || tl >= qr) {
return;
}
if (ql <= tl && tr <= qr) {
tree[v].l = max(tree[v].l, val);
tree[v].r = max(tree[v].r, tree[v].l);
tree[v].l = min(tree[v].l, tree[v].r);
return;
}
push(v, tl, tr);
int tm = (tl + tr) >> 1;
update1(left, tl, tm, ql, qr, val);
update1(right, tm, tr, ql, qr, val);
}
void update2 (int v, int tl, int tr, int ql, int qr, int val) {
if (ql >= tr || tl >= qr) {
return;
}
if (ql <= tl && tr <= qr) {
tree[v].r = max(tree[v].r, tree[v].l);
tree[v].r = min(tree[v].r, val);
tree[v].l = min(tree[v].l, tree[v].r);
return;
}
push(v, tl, tr);
int tm = (tl + tr) >> 1;
update2(left, tl, tm, ql, qr, val);
update2(right, tm, tr, ql, qr, val);
}
ll get (int v, int tl, int tr, int pos) {
if (tl + 1 == tr) {
return tree[v].l;
}
push(v, tl, tr);
int tm = (tl + tr) >> 1;
if (pos < tm) return get(left, tl, tm, pos);
return get(right, tm, tr, pos);
}
};
void buildWall (int N, int K, int op[], int L[], int R[], int height[], int finalHeight[]) {
vector<int> arr(N, 0);
Lazy_Segtree LST;
LST.init(N + 10);
LST.built(0, 0, N, arr);
for (int i = 0;i < K;i ++) {
if (op[i] == 1) {
LST.update1(0, 0, N, L[i], R[i] + 1, height[i]);
} else {
LST.update2(0, 0, N, L[i], R[i] + 1, height[i]);
}
// for (int j = 0;j < N;j ++) cout << LST.get(0, 0, N, j) << " ";
// cout << "\n";
}
for (int i = 0;i < N;i ++) finalHeight[i] = LST.get(0, 0, N, i);
}
