#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int inf = 0x3f3f3f3f;
void minSelf(int &x, int y) {
if (y < x) {
x = y;
}
}
void maxSelf(int &x, int y) {
if (y > x) {
x = y;
}
}
struct SegTree {
struct Node {
int mini, maxi;
};
int n;
vector <Node> v;
void build(int nod, int st, int dr) {
v[nod].mini = 0;
v[nod].maxi = inf;
if (st == dr) {
return;
}
int med = (st + dr) / 2;
build(2 * nod, st, med);
build(2 * nod + 1, med + 1, dr);
}
void minimize(int nod, int val) {
if (val < v[nod].mini) {
v[nod].mini = val;
v[nod].maxi = val;
} else if (val < v[nod].maxi) {
v[nod].maxi = val;
}
}
void maximize(int nod, int val) {
if (val > v[nod].maxi) {
v[nod].mini = val;
v[nod].maxi = val;
} else if (val > v[nod].mini) {
v[nod].mini = val;
}
}
void propag(int nod) {
minimize(2 * nod, v[nod].maxi);
maximize(2 * nod, v[nod].mini);
minimize(2 * nod + 1, v[nod].maxi);
maximize(2 * nod + 1, v[nod].mini);
v[nod].mini = 0;
v[nod].maxi = inf;
}
void update(int nod, int st, int dr, int ust, int udr, int val, int type) {
if (ust <= st && dr <= udr) {
if (type == 1) {
maximize(nod, val);
} else {
minimize(nod, val);
}
return;
}
propag(nod);
int med = (st + dr) / 2;
if (ust <= med) {
update(2 * nod, st, med, ust, udr, val, type);
}
if (med < udr) {
update(2 * nod + 1, med + 1, dr, ust, udr, val, type);
}
}
void update(int ust, int udr, int val, int type) {
update(1, 1, n, ust, udr, val, type);
}
int getVal(int nod, int st, int dr, int poz) {
if (st == dr) {
return clamp(0, v[nod].mini, v[nod].maxi);
}
int med = (st + dr) / 2, x;
if (poz <= med) {
x = getVal(2 * nod, st, med, poz);
} else {
x = getVal(2 * nod + 1, med + 1, dr, poz);
}
return clamp(x, v[nod].mini, v[nod].maxi);
}
void print(int nod, int st, int dr, int ans[]) {
if (st == dr) {
ans[st - 1] = clamp(0, v[nod].mini, v[nod].maxi);
return;
}
propag(nod);
int med = (st + dr) / 2;
print(2 * nod, st, med, ans);
print(2 * nod + 1, med + 1, dr, ans);
}
void print(int ans[]) {
print(1, 1, n, ans);
}
SegTree(int n_) : n(n_), v(4 * n + 1) {
build(1, 1, n);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
SegTree aint(n);
for (int i = 0; i < k; i++) {
aint.update(left[i] + 1, right[i] + 1, height[i], op[i]);
}
aint.print(finalHeight);
}
