#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
const int MN = 2e6+5;
#define lc ind<<1
#define rc ind<<1|1
struct Node {
int l,r,mx,mn;
} tree[MN<<2];
int ans[MN];
int le[MN], ri[MN], o[MN], he[MN], f[MN];
void build (int ind, int l, int r) {
tree[ind] = {l,r,0,INT_MAX};
if (l == r) return;
int mid = (l+r)>>1;
build(lc,l,mid), build(rc,mid+1,r);
}
void remove (int ind, int v) {
tree[ind].mn = min(tree[ind].mn,v);
tree[ind].mx = min(tree[ind].mx,v);
}
void add (int ind, int v) {
tree[ind].mx = max(tree[ind].mx,v);
tree[ind].mn = max(tree[ind].mn,v);
}
void push_down (int ind) {
if (tree[ind].l == tree[ind].r) return;
add(lc,tree[ind].mx);
remove(lc,tree[ind].mn);
add(rc,tree[ind].mx);
remove(rc,tree[ind].mn);
tree[ind].mx = 0, tree[ind].mn = INT_MAX;
}
void update (int ind, int l, int r, bool op, int v) {
if (tree[ind].l > r || tree[ind].r < l) return;
if (tree[ind].l >= l && tree[ind].r <= r) {
op ? remove(ind,v) : add(ind,v);
return;
}
push_down(ind);
update(lc,l,r,op,v);
update(rc,l,r,op,v);
}
void finish (int ind) {
if (tree[ind].l == tree[ind].r) {
ans[tree[ind].l] = min(tree[ind].mn,tree[ind].mx);
return;
}
push_down(ind);
finish (lc); finish (rc);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
build(1,0,n-1);
for (int i = 0; i < k; i++) {
update(1,left[i],right[i],op[i] == 2,height[i]);
}
finish(1);
for (int i = 0; i < n; i++) finalHeight[i] = ans[i];
}
