#include "bits/stdc++.h"
#include "wall.h"
using namespace std;
template <class T, class U, int SIZE>
struct LazySegTree {
static_assert(__builtin_popcount(SIZE) == 1);
const T kOpId = 0;
const U kLazyId_1 = -1, kLazyId_2 = 1 << 17;
T Op(T a, T b) {
return max(a, b);
}
T tree[2 * SIZE];
U lazy_1[2 * SIZE], lazy_2[2 * SIZE];
LazySegTree() {
for (int i = 0; i < 2 * SIZE; ++i)
tree[i] = kOpId, lazy_1[i] = kLazyId_1, lazy_2[i] = kLazyId_2;
}
void Push(int cur, int low, int high) {
int mid = (low + high) / 2;
if (lazy_1[cur] != kLazyId_1) {
Max(low, high, lazy_1[cur], 2 * cur, low, mid),
Max(low, high, lazy_1[cur], 2 * cur + 1, mid + 1, high);
lazy_1[cur] = kLazyId_1;
}
if (lazy_2[cur] != kLazyId_2) {
Min(low, high, lazy_2[cur], 2 * cur, low, mid),
Min(low, high, lazy_2[cur], 2 * cur + 1, mid + 1, high);
lazy_2[cur] = kLazyId_2;
}
}
void Pull(int cur) {
tree[cur] = Op(tree[2 * cur], tree[2 * cur + 1]);
}
void Max(int l, int r, U val, int cur = 1, int low = 0, int high = SIZE - 1) {
if (r < low || high < l)
return;
if (l <= low && high <= r) {
tree[cur] = max(tree[cur], val);
if (val > lazy_2[cur])
lazy_1[cur] = lazy_2[cur] = val;
else
lazy_1[cur] = max(lazy_1[cur], val);
return;
}
Push(cur, low, high);
int mid = (low + high) / 2;
Max(l, r, val, 2 * cur, low, mid),
Max(l, r, val, 2 * cur + 1, mid + 1, high);
Pull(cur);
}
void Min(int l, int r, U val, int cur = 1, int low = 0, int high = SIZE - 1) {
if (r < low || high < l)
return;
if (l <= low && high <= r) {
tree[cur] = min(tree[cur], val);
lazy_2[cur] = min(lazy_2[cur], val);
return;
}
Push(cur, low, high);
int mid = (low + high) / 2;
Min(l, r, val, 2 * cur, low, mid),
Min(l, r, val, 2 * cur + 1, mid + 1, high);
Pull(cur);
}
T Qry(int l, int r, int cur = 1, int low = 0, int high = SIZE - 1) {
if (r < low || high < l)
return kOpId;
if (l <= low && high <= r)
return tree[cur];
Push(cur, low, high);
int mid = (low + high) / 2;
return Op(
Qry(l, r, 2 * cur, low, mid),
Qry(l, r, 2 * cur + 1, mid + 1, high)
);
}
};
const int kSize = 1 << 21;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
LazySegTree<int, int, kSize> tree;
for (int i = 0; i < k; ++i) {
if (op[i] == 1)
tree.Max(left[i], right[i], height[i]);
else
tree.Min(left[i], right[i], height[i]);
}
for (int i = 0; i < n; ++i)
finalHeight[i] = tree.Qry(i, i);
}
