#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6+100;
const int oo = 1e9;
int n;
pair<int,int> t[N<<2];
int getHeight(pair<int,int> v, int init = 0) {
return max(min(init, v.first), v.second);
}
void add(pair<int,int> &tmp, int h) {
tmp.second = max(tmp.second, h);
tmp.first = max(tmp.first, tmp.second);
}
void rem(pair<int,int> &tmp, int h) {
tmp.first = min(tmp.first, h);
tmp.second = min(tmp.first, tmp.second);
}
void shift(int node, int L, int R) {
int lc = node << 1, rc = lc | 1;
rem(t[lc], t[node].first);
add(t[lc], t[node].second);
rem(t[rc], t[node].first);
add(t[rc], t[node].second);
t[node] = {oo, 0};
}
void build(int node, int L, int R) {
t[node] = {oo, 0};
if(L == R) return;
int mid = (L + R) >> 1, lc = node << 1, rc = lc | 1;
build(lc, L, mid); build(rc, mid + 1, R);
}
void upd(int node, int L, int R, int op, int l, int r, int h) {
if(r < L || R < l) return;
if(l <= L && R <= r) {
if(op == 1) add(t[node], h);
else rem(t[node], h);
return;
} shift(node, L, R);
int mid = (L + R) >> 1, lc = node << 1, rc = lc | 1;
upd(lc, L, mid, op, l, r, h);
upd(rc, mid + 1, R, op, l, r, h);
}
int soln[N];
void retrieve(int node, int L, int R) {
if(L == R) return void(soln[L] = getHeight(t[node]));
shift(node, L, R);
int mid = (L + R) >> 1, lc = node << 1, rc = lc | 1;
retrieve(lc, L, mid); retrieve(rc, mid + 1, R);
}
void buildWall(int _n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
n = _n;
build(1, 0, n - 1);
for(int i = 0; i < k; i++)
upd(1, 0, n - 1, op[i], left[i], right[i], height[i]);
retrieve(1, 0, n - 1);
for(int i = 0; i < n; i++)
finalHeight[i] = soln[i];
}
