// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
#define SZ(x) (int) x.size()
#define F first
#define S second
#define lc id << 1
#define rc lc | 1
const int N = 2e6 + 10;
int mx[N << 2], mn[N << 2], lz[N << 2], _n, k;
void shift(int id, int l, int r) {
if (lz[id] < 0) return;
mx[id] = mn[id] = lz[id];
if (r - l > 1) {
lz[lc] = lz[rc] = lz[id];
}
lz[id] = -1;
}
void setmin(int ql, int qr, int x, int id = 1, int l = 0, int r = _n) {
shift(id, l, r);
if (qr <= l || r <= ql || mx[id] <= x) return;
if (ql <= l && r <= qr && mn[id] >= x) {
lz[id] = x;
return shift(id, l, r);
}
int mid = (l + r) >> 1;
setmin(ql, qr, x, lc, l, mid);
setmin(ql, qr, x, rc, mid, r);
mn[id] = min(mn[lc], mn[rc]);
mx[id] = max(mx[lc], mx[rc]);
}
void setmax(int ql, int qr, int x, int id = 1, int l = 0, int r = _n) {
shift(id, l, r);
if (qr <= l || r <= ql || mn[id] >= x) return;
if (ql <= l && r <= qr && mx[id] <= x) {
lz[id] = x;
return shift(id, l, r);
}
int mid = (l + r) >> 1;
setmax(ql, qr, x, lc, l, mid);
setmax(ql, qr, x, rc, mid, r);
mn[id] = min(mn[lc], mn[rc]);
mx[id] = max(mx[lc], mx[rc]);
}
int print(int pos, int id = 1, int l = 0, int r = _n) {
shift(id, l, r);
if (r - l < 2) {
return mx[id];
}
int mid = (l + r) >> 1;
if (pos < mid) return print(pos, lc, l, mid);
else return print(pos, rc, mid, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
memset(lz, -1, sizeof lz);
_n = n;
for (int i = 0; i < k; i++) {
int t = op[i], l = left[i], r = right[i], h = height[i];
if (t == 1) setmax(l, r + 1, h);
else setmin(l, r + 1, h);
}
for (int i = 0; i < n; i++) finalHeight[i] = print(i);
return;
}
