#include <bits/stdc++.h>
#include "wall.h"
#define fi first
#define se second
using namespace std;
const int MXn = 2e6 + 5, oo = 1e5;
int N;
struct type {
int LL, RR;
} node[(1 << 22) + 5];
void build(int id = 1, int l = 0, int r = N) {
if (l == r) {
node[id] = {0, 0};
return;
}
node[id] = {0, oo};
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
}
void modify(int id, int t, int val) {
// if (val == 3 && id == 24) cerr << t << ' ' << node[id].LL << ' ' << node[id].RR << '\n';
if (t == 1) {
// if (node[id].RR < val) node[id].b = true;
node[id].LL = max(node[id].LL, val);
node[id].RR = max(node[id].RR, val);
} else {
// if (node[id].LL > val) node[id].b = false;
node[id].LL = min(node[id].LL, val);
node[id].RR = min(node[id].RR, val);
}
// if (val == 3 && id == 24) cerr << t << ' ' << node[id].LL << ' ' << node[id].RR << '\n';
}
void push(int id) {
// if (node[id].b) {
modify(id << 1, 1, node[id].LL);
modify(id << 1, 2, node[id].RR);
modify(id << 1 | 1, 1, node[id].LL);
modify(id << 1 | 1, 2, node[id].RR);
// } else {
// modify(id << 1, 2, node[id].LL);
// modify(id << 1, 1, node[id].RR);
// modify(id << 1 | 1, 2, node[id].LL);
// modify(id << 1 | 1, 1, node[id].RR);
// }
node[id] = {0, oo};
}
void update(int t, int Lf, int Rt, int val, int id = 1, int l = 0, int r = N) {
if (Lf <= l && r <= Rt) {
modify(id, t, val);
return;
}
push(id);
int mid = (l + r) >> 1;
if (Lf <= mid) update(t, Lf, Rt, val, id << 1, l, mid);
if (Rt > mid) update(t, Lf, Rt, val, id << 1 | 1, mid + 1, r);
}
int findh(int i) {
int id = 1, l = 0, r = N;
while (l < r) {
push(id);
int mid = (l + r) >> 1;
if (i <= mid) {
id <<= 1;
r = mid;
} else {
id = id << 1 | 1;
l = mid + 1;
}
}
return node[id].LL;
}
void buildWall(int w, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
N = w - 1;
build();
for (int i = 0; i < k; i++) update(op[i], left[i], right[i], height[i]);
for (int i = 0; i < w; i++) finalHeight[i] = findh(i);
}
