/**
* author: milos
* created: 01.01.2021 04:18:07
**/
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 5;
struct segtree{
int mn[N], mx[N], a[N];
void build(int c, int x, int y) {
if (mn[c] == 1e9) {
return;
}
mn[c] = 1e9, mx[c] = 0, a[c] = 0;
if (x >= y) {
return;
}
int mid = x + y >> 1;
build(c * 2 + 1, x, mid);
build(c * 2 + 2, mid + 1, y);
}
void push(int c, int x, int y) {
a[c] = max(a[c], mx[c]);
a[c] = min(a[c], mn[c]);
if (x != y) {
mx[2 * c + 1] = max(mx[c * 2 + 1], mx[c]);
mx[2 * c + 1] = min(mx[c * 2 + 1], mn[c]);
mn[2 * c + 1] = max(mn[c * 2 + 1], mx[c]);
mn[2 * c + 1] = min(mn[c * 2 + 1], mn[c]);
mx[2 * c + 2] = max(mx[c * 2 + 2], mx[c]);
mx[2 * c + 2] = min(mx[c * 2 + 2], mn[c]);
mn[2 * c + 2] = max(mn[c * 2 + 2], mx[c]);
mn[2 * c + 2] = min(mn[c * 2 + 2], mn[c]);
}
mn[c] = 1e9, mx[c] = 0;
}
void add(int c, int x, int y, int l, int r, int val) {
push(c, x, y);
if (x > y || x > r || y < l) {
return;
}
if (x >= l && y <= r) {
mx[c] = val;
return;
}
int mid = x + y >> 1;
add(c * 2 + 1, x, mid, l, r, val);
add(c * 2 + 2, mid + 1, y, l, r, val);
}
void del(int c, int x, int y, int l, int r, int val) {
push(c, x, y);
if (x > y || x > r || y < l) {
return;
}
if (x >= l && y <= r) {
mn[c] = val;
return;
}
int mid = x + y >> 1;
del(c * 2 + 1, x, mid, l, r, val);
del(c * 2 + 2, mid + 1, y, l, r, val);
}
} st;
vector<int> ans;
void Solve(int c, int l, int r) {
if (l > r) {
return;
}
st.push(c, l, r);
if (l == r) {
ans.push_back(st.a[c]);
return;
}
int mid = l + r >> 1;
Solve(c * 2 + 1, l, mid);
Solve(c * 2 + 2, mid + 1, r);
}
void buildWall(int n, int q, int* op, int* left, int* right, int* height, int* finalHeight) {
st.build(0, 0, n - 1);
for (int i = 0; i < q; i++) {
if (op[i] == 1) {
st.add(0, 0, n - 1, left[i], right[i], height[i]);
} else {
st.del(0, 0, n - 1, left[i], right[i], height[i]);
}
}
Solve(0, 0, n - 1);
for (int i = 0; i < n; i++) {
finalHeight[i] = ans[i];
}
}
