#include "wall.h"
#include <bits/stdc++.h>
struct Item {
int max;
int min;
Item() : max(1 << 30), min(-1) { }
void merge_max(int value) {
max = std::min(max, value);
min = std::min(min, max);
}
void merge_min(int value) {
min = std::max(min, value);
max = std::max(max, min);
}
void merge(const Item& oth) {
max = std::min(max, oth.max);
min = std::min(min, max);
min = std::max(min, oth.min);
max = std::max(max, min);
}
void merge(const Item& oth_a, const Item& oth_b) {
max = std::min(oth_a.max, oth_b.max);
min = std::max(oth_a.min, oth_b.min);
max = std::max(max, min);
min = std::min(min, max);
}
};
struct Seg {
int size;
std::vector <Item> v, lazy;
Seg(int _size) {
size = 1;
while (size < _size) size <<= 1;
v.resize(size << 1, Item());
lazy.resize(size << 1, Item());
}
void update(bool type, int value, int target_left, int target_right, int now, int left, int right) {
if (lazy[now].max != 1 << 30 || lazy[now].min != -1) {
v[now].merge(lazy[now]);
if (right - left - 1) {
lazy[now * 2 + 1].merge(lazy[now]);
lazy[now * 2 + 2].merge(lazy[now]);
}
lazy[now] = Item();
}
if (left >= target_right || right <= target_left)
return;
if (left >= target_left && right <= target_right) {
if (type)
v[now].merge_max(value);
else
v[now].merge_min(value);
if (right - left - 1) {
if (type)
lazy[now * 2 + 1].merge_max(value),
lazy[now * 2 + 2].merge_max(value);
else
lazy[now * 2 + 1].merge_min(value),
lazy[now * 2 + 2].merge_min(value);
}
return;
}
int mid = (left + right) >> 1;
update(type, value, target_left, target_right, now * 2 + 1, left, mid);
update(type, value, target_left, target_right, now * 2 + 2, mid, right);
v[now].merge(v[now * 2 + 1], v[now * 2 + 2]);
}
void update(bool type, int value, int left, int right) {
update(type, value, left, right, 0, 0, size);
}
int get(int index, int now, int left, int right) {
if (lazy[now].max != 1 << 30 || lazy[now].min != -1) {
v[now].merge(lazy[now]);
if (right - left - 1) {
lazy[now * 2 + 1].merge(lazy[now]);
lazy[now * 2 + 2].merge(lazy[now]);
}
lazy[now] = Item();
}
if (!(right - left - 1))
return std::max(0, v[now].min);
int mid = (left + right) >> 1;
if (index < mid)
return get(index, now * 2 + 1, left, mid);
return get(index, now * 2 + 2, mid, right);
}
int get(int index) {
return get(index, 0, 0, size);
}
void print() {
int cnt = 2;
for (int i = 0; i < (int)v.size(); i++) {
if (i == cnt - 1) {
cnt <<= 1;
std::cout << "\n";
}
std::cout << v[i].min << " ";
}
std::cout << "\n";
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
Seg seg(n);
for (int i = 0; i < k; i++)
seg.update(!op[i], height[i], left[i], right[i] + 1);
for (int i = 0; i < n; i++) finalHeight[i] = seg.get(i);
}
