#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
const int INF = 1e8;
int N;
vector<pair<int,int>> tree;
pair<int,int> merge(pair<int,int> &a, pair<int,int> b) {
if (b.F > a.S) return a = {b.F, b.F};
if (b.S < a.F) return a = {b.S, b.S};
return a = {max(a.F, b.F), min(a.S, b.S)};
}
void pushdown(int tl, int tr, int i) {
if (tl != tr) {
merge(tree[i*2], tree[i]);
merge(tree[i*2+1], tree[i]);
tree[i] = {0, INF};
}
}
void update(pair<int,int> v, int l, int r, int tl = 0, int tr = N-1, int i = 1) {
pushdown(tl, tr, i);
if (l > r) return;
if (tl == l && tr == r) {
merge(tree[i], v);
pushdown(tl, tr, i);
return;
}
int tm = (tl + tr) / 2;
update(v, l, min(r, tm), tl, tm, i * 2);
update(v, max(l, tm + 1), r, tm + 1, tr, i * 2 + 1);
}
int query(int p, int tl = 0, int tr = N-1, int i = 1) {
pushdown(tl, tr, i);
if (tl == tr) return tree[i].F;
int tm = (tl + tr) / 2;
if (p <= tm) return query(p, tl, tm, i * 2);
else return query(p, tm + 1, tr, i * 2 + 1);
}
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
::N = N;
tree.resize(4*N, {0, INF});
for(int i = 0; i < K; i++) {
if (op[i] == 1) update({height[i], INF}, left[i], right[i]);
if (op[i] == 2) update({0, height[i]}, left[i], right[i]);
}
for(int i = 0; i < N; i++) {
finalHeight[i] = query(i);
}
}
