#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
int lowv[4000005];
int highv[4000005];
// add operation: max(value, h)
void applyMax(int node, int h) {
lowv[node] = max(lowv[node], h);
highv[node] = max(highv[node], h);
}
// remove operation: min(value, h)
void applyMin(int node, int h) {
lowv[node] = min(lowv[node], h);
highv[node] = min(highv[node], h);
}
void push(int node) {
int L = node * 2;
int R = node * 2 + 1;
// előbb max, utána min logikusan kezelve
applyMax(L, lowv[node]);
applyMin(L, highv[node]);
applyMax(R, lowv[node]);
applyMin(R, highv[node]);
// reset
lowv[node] = 0;
highv[node] = INF;
}
void update(
int node,
int start,
int end,
int l,
int r,
int type,
int h
) {
if (r < start || end < l) return;
if (l <= start && end <= r) {
if (type == 1) applyMax(node, h); // add
else if (type == 2) applyMin(node, h); // remove
return;
}
push(node);
int mid = (start + end) / 2;
update(node * 2, start, mid, l, r, type, h);
update(node * 2 + 1, mid + 1, end, l, r, type, h);
}
// végső értékek kiolvasása
void collect(
int node,
int start,
int end,
int result[]
) {
if (start == end) {
result[start] = lowv[node];
return;
}
push(node);
int mid = (start + end) / 2;
collect(node * 2, start, mid, result);
collect(node * 2 + 1, mid + 1, end, result);
}
void buildWall(
int n,
int k,
int op[],
int left[],
int right[],
int height[],
int finalHeight[]
) {
// kezdetben minden 0, nincs felső korlát
for (int i = 0; i < 4 * n; i++) {
lowv[i] = 0;
highv[i] = INF;
}
for (int i = 0; i < k; i++) {
update(
1,
0,
n - 1,
left[i],
right[i],
op[i],
height[i]
);
}
collect(1, 0, n - 1, finalHeight);
for (int i=0; i<n; i++){
cout << finalHeight[i] << " ";
}
}
int main(){
int op[] = {1, 2, 2};
int left[] = {1, 4, 3};
int right[] = {8, 9, 6};
int height[] = {4, 1, 5};
int finalHeight[10] = {};
buildWall(10, 3, op, left, right, height, finalHeight);
}
