#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2000 * 1000 + 5;
int n;
pair <int, int> smin[N * 4], smax[N * 4];
void apply(int id, int qt, int h, int t) {
if (t == 0) {
return;
}
if (qt == 1) {
if (h < smax[id].first && smin[id].second > smax[id].second && smin[id].first < h) {
smax[id] = {h, t};
}
else {
smax[id] = max(smax[id], {h, t});
}
}
else {
if (h >= smin[id].first && smin[id].second < smax[id].second && smax[id].first > h) {
smin[id] = {h, t};
}
else {
smin[id] = min(smin[id], {h, t});
}
}
}
void shift(int id) {
if (smin[id].second <= smax[id].second) {
apply(id * 2, 2, smin[id].first, smin[id].second);
apply(id * 2, 1, smax[id].first, smax[id].second);
apply(id * 2 + 1, 2, smin[id].first, smin[id].second);
apply(id * 2 + 1, 1, smax[id].first, smax[id].second);
}
else {
apply(id * 2, 1, smax[id].first, smax[id].second);
apply(id * 2, 2, smin[id].first, smin[id].second);
apply(id * 2 + 1, 1, smax[id].first, smax[id].second);
apply(id * 2 + 1, 2, smin[id].first, smin[id].second);
}
smin[id] = {N, 0};
smax[id] = {0, 0};
}
void update(int qt, int l, int r, int h, int t, int id = 1, int s = 0, int e = n) {
if (r <= s || e <= l) {
return;
}
if (l <= s && e <= r) {
// cout << "72 " << id << " " << s << " " << e << " " << l << " " << r << endl;
apply(id, qt, h, t);
return;
}
int md = (s + e) / 2;
shift(id);
update(qt, l, r, h, t, id * 2, s, md);
update(qt, l, r, h, t, id * 2 + 1, md, e);
}
int get(int p, int id = 1, int s = 0, int e = n) {
if (e - s == 1) {
if (smax[id].second >= smin[id].second || smax[id].first <= smin[id].first) {
return smax[id].first;
}
return smin[id].first;
}
shift(id);
int md = (s + e) / 2;
if (p < md) {
return get(p, id * 2, s, md);
}
return get(p, id * 2 + 1, md, e);
}
void buildWall(int m, int q, int op[], int left[], int right[], int height[], int finalHeight[]){
n = m;
for (int i = 0; i < q; i++) {
update(op[i], left[i], right[i] + 1, height[i], i + 1);
}
for (int i = 0; i < n; i++) {
finalHeight[i] = get(i);
}
}
