#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
const int mxN = 2e6 + 1;
int seg[4 * mxN];
pii lazy[4 * mxN];
bool marked[4 * mxN];
int n;
pii merge(pii a, pii b) {
if (min({a.ff, a.ss, b.ff, b.ss}) == -1 || max({a.ff, a.ss, b.ff, b.ss}) == 1e5 + 1) {
a.ff = max(a.ff, b.ff);
a.ss = min(a.ss, b.ss);
if (a.ff > a.ss) {
if (b.ff > a.ss) return {b.ff, b.ff};
else if (b.ss < a.ff) return {b.ss, b.ss};
}
return a;
}
if (a.ss < b.ff) {
return {b.ff, b.ff};
} else if (b.ss < a.ff) {
return {b.ss, b.ss};
}
a.ff = max(a.ff, b.ff);
a.ss = min(a.ss, b.ss);
if (a.ff > a.ss) {
if (b.ff > a.ss) return {b.ff, b.ff};
else if (b.ss < a.ff) return {b.ss, b.ss};
}
return a;
}
void pushdown(int idx) {
if (marked[idx]) {
seg[(idx << 1)] = max(seg[(idx << 1)], lazy[idx].ff);
seg[(idx << 1)] = min(seg[(idx << 1)], lazy[idx].ss);
seg[(idx << 1) + 1] = max(seg[(idx << 1) + 1], lazy[idx].ff);
seg[(idx << 1) + 1] = min(seg[(idx << 1) + 1], lazy[idx].ss);
lazy[(idx << 1)] = merge(lazy[(idx << 1)], lazy[idx]);
lazy[(idx << 1) + 1] = merge(lazy[(idx << 1) + 1], lazy[idx]);
lazy[idx] = {-1, 1e6 + 1};
marked[(idx << 1)] = true;
marked[(idx << 1) + 1] = true;
marked[idx] = false;
}
}
void update(int tl, int tr, bool ismin, int val, int l = 1, int r = n, int idx = 1) {
if (l > r) return;
if (tl <= l && r <= tr) {
if (ismin) {
seg[idx] = min(seg[idx], val);
lazy[idx].ss = min(lazy[idx].ss, val);
if (lazy[idx].ff > lazy[idx].ss) {
lazy[idx].ff = lazy[idx].ss;
}
} else {
seg[idx] = max(seg[idx], val);
lazy[idx].ff = max(lazy[idx].ff, val);
if (lazy[idx].ff > lazy[idx].ss) {
lazy[idx].ss = lazy[idx].ff;
}
}
marked[idx] = true;
return;
}
pushdown(idx);
int mid = (l + r) >> 1;
if (tl <= mid) update(tl, min(tr, mid), ismin, val, l, mid, (idx << 1));
if (tr > mid) update(max(tl, mid + 1), tr, ismin, val, mid + 1, r, (idx << 1) + 1);
return;
}
int query(int tar, int l = 1, int r = n, int idx = 1) {
if (l > r) return -1;
if (l == r) return seg[idx];
pushdown(idx);
int mid = (l + r) >> 1;
if (tar <= mid) return query(tar, l, mid, (idx << 1));
else return query(tar, mid + 1, r, (idx << 1) + 1);
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
n = N;
for (int i = 0; i < 4 * mxN; i++) {
seg[i] = 0;
lazy[i] = {-1, 1e6 + 1};
}
for (int i = 0; i < k; i++) {
update(left[i] + 1, right[i] + 1, (op[i] == 2), height[i]);
}
for (int i = 0; i < n; i++) {
finalHeight[i] = query(i + 1);
}
return;
}
