#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
using pii = pair<int, int>;
struct SegTree {
int n;
vector<int> tree;
vector<pii> lazy;
SegTree(int _n) {
n = _n;
tree.resize(4*n+5, 0);
lazy.resize(4*n+5, {1e9, -1});
}
void push(int u, int tl, int tr) {
if(tl == tr) return ;
if(lazy[u].first != 1e9) {
tree[2*u] = min(tree[2*u], lazy[u].first);
lazy[2*u].first = min(lazy[2*u].first, lazy[u].first);
lazy[2*u].second = min(lazy[2*u].second, lazy[u].first);
tree[2*u+1] = min(tree[2*u+1], lazy[u].first);
lazy[2*u+1].first = min(lazy[2*u+1].first, lazy[u].first);
lazy[2*u+1].second = min(lazy[2*u+1].second, lazy[u].first);
}
if(lazy[u].second != -1) {
tree[2*u] = max(tree[2*u], lazy[u].second);
lazy[2*u].first = max(lazy[2*u].first, lazy[u].second);
lazy[2*u].second = max(lazy[2*u].second, lazy[u].second);
tree[2*u+1] = max(tree[2*u+1], lazy[u].second);
lazy[2*u+1].first = max(lazy[2*u+1].first, lazy[u].second);
lazy[2*u+1].second = max(lazy[2*u+1].second, lazy[u].second);
}
lazy[u] = {1e9, -1};
}
void update(int u, int tl, int tr, int l, int r, int t, int v) {
push(u, tl, tr);
if(tl > tr || l > tr || tl > r) return ;
if(l <= tl && tr <= r) {
if(t == 1) {
tree[u] = max(tree[u], v);
lazy[u].first = max(lazy[u].first, v);
lazy[u].second = max(lazy[u].second, v);
} else {
tree[u] = min(tree[u], v);
lazy[u].first = min(lazy[u].first, v);
lazy[u].second = min(lazy[u].second, v);
}
push(u, tl, tr);
return ;
}
int tm = (tl + tr) / 2;
update(2*u, tl, tm, l, r, t, v);
update(2*u+1, tm+1, tr, l, r, t, v);
}
int query(int u, int tl, int tr, int p) {
if(tl == tr) return tree[u];
push(u, tl, tr);
int tm = (tl + tr) / 2;
if(p <= tm) return query(2*u, tl, tm, p);
return query(2*u+1, tm+1, tr, p);
}
void update(int l, int r, int t, int v) { update(1, 0, n-1, l, r, t, v); }
int query(int p) { return query(1, 0, n-1, p); }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
SegTree tree(n);
for(int i=0; i<k; i++) tree.update(left[i], right[i], op[i], height[i]);
for(int i=0; i<n; i++) finalHeight[i] = tree.query(i);
}
