#include "wall.h"
#include <algorithm>
#define MAXN 2000000
#define MAXP 4200000
#define INF 100000
int atLeast[MAXP], atMost[MAXP], ans[MAXN], left, right, h, tip;
inline void unu(int p, int h) {
atLeast[p] = std::max(atLeast[p], h);
atMost[p] = std::max(atMost[p], atLeast[p]);
}
inline void doi(int p, int h) {
atMost[p] = std::min(atMost[p], h);
atLeast[p] = std::min(atLeast[p], atMost[p]);
}
inline void propag(int p, int st, int dr) {
unu(st, atLeast[p]);
doi(st, atMost[p]);
unu(dr, atLeast[p]);
doi(dr, atMost[p]);
atLeast[p] = 0;
atMost[p] = INF;
}
void update(int p, int st, int dr) {
if (left <= st && dr <= right) {
if (tip == 1)
unu(p, h);
else
doi(p, h);
} else {
propag(p, 2 * p, 2 * p + 1);
int m = (st + dr) / 2;
if (left <= m) update(2 * p, st, m);
if (m < right) update(2 * p + 1, m + 1, dr);
}
}
void dfs(int p, int st, int dr) {
if (st == dr)
ans[st] = atLeast[p];
else {
propag(p, 2 * p, 2 * p + 1);
int m = (st + dr) / 2;
dfs(2 * p, st, m);
dfs(2 * p + 1, m + 1, dr);
}
}
void buildWall(int n, int k, int op[], int left0[], int right0[], int height[], int finalHeight[]) {
for (int i = 0; i < k; i++) {
tip = op[i];
left = left0[i];
right = right0[i];
h = height[i];
update(1, 0, n - 1);
}
dfs(1, 0, n - 1);
for (int i = 0; i < n; i++)
finalHeight[i] = ans[i];
}
