#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e5;
const int inf = 1 << 30;
static int v[nmax + 1];
static int aint[4 * nmax + 1];
void update_max (int nod, int x, int y, int st, int dr, int val) {
if (st <= x && y <= dr) {
aint[nod] = max(aint[nod], val);
return ;
}
int mij = (x + y) / 2;
if (st <= mij)
update_max(2 * nod, x, mij, st, dr, val);
if (mij < dr)
update_max(2 * nod + 1, mij + 1, y, st, dr, val);
}
void update_min (int nod, int x, int y, int st, int dr, int val) {
if (st <= x && y <= dr) {
aint[nod] = min(aint[nod], val);
return ;
}
int mij = (x + y) / 2;
if (st <= mij)
update_min(2 * nod, x, mij, st, dr, val);
if (mij < dr)
update_min(2 * nod + 1, mij + 1, y, st, dr, val);
}
void build (int nod, int x, int y) {
aint[nod] = inf;
if (x == y)
return ;
int mij = (x + y) / 2;
build(2 * nod, x, mij);
build(2 * nod + 1, mij + 1, y);
}
void dfs_min (int nod, int x, int y, int val = inf) {
val = min(val, aint[nod]);
if (x == y) {
v[x] = min(val, v[x]);
return ;
}
int mij = (x + y) / 2;
dfs_min(2 * nod, x, mij, val);
dfs_min(2 * nod + 1, mij + 1, y, val);
}
void dfs_max (int nod, int x, int y, int val = -inf) {
val = max(val, aint[nod]);
if (x == y) {
v[x] = max(val, v[x]);
return ;
}
int mij = (x + y) / 2;
dfs_max(2 * nod, x, mij, val);
dfs_max(2 * nod + 1, mij + 1, y, val);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
if (n <= 10000 && k <= 5000) {
for (int i = 0; i < k; ++ i) {
for (int j = left[i]; j <= right[i]; ++ j) {
if (op[i] == 1)
v[j] = max(v[j], height[i]);
else
v[j] = min(v[j], height[i]);
}
}
} else {
int ind = 0;
while (ind < k && op[ind] == 1) {
update_max(1, 0, n - 1, left[ind], right[ind], height[ind]);
++ ind;
}
dfs_max(1, 0, n - 1);
build(1, 0, n - 1);
while (ind < k) {
update_min(1, 0, n - 1, left[ind], right[ind], height[ind]);
++ ind;
}
dfs_min(1, 0, n - 1);
}
for (int i = 0; i < n; ++ i)
finalHeight[i] = v[i];
return;
}
