#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
struct node {
node *lf, *rg;
int l, r;
int val, lzMin, lzMax;
node(int x, int y): l(x), r(y), val(0), lzMin(INF), lzMax(-INF) {}
void build() {
if (l == r) return;
int mid = (l+r)/2;
lf = new node(l,mid); lf->build();
rg = new node(mid+1,r); rg->build();
}
void apply(int mn, int mx) {
val = min(val,mn); lzMin = min(lzMin,mn);
val = max(val,mx); lzMax = max(lzMax,mx);
}
void prop() {
if (lzMin == INF && lzMax == -INF) return;
if (l < r) {
lf->apply(lzMin,lzMax);
rg->apply(lzMin,lzMax);
}
lzMin = INF, lzMax = -INF;
}
void update(int x, int y, int mn, int mx) {
if (l > y || r < x) return;
if (l >= x && r <= y) {
apply(mn,mx);
return;
}
prop();
lf->update(x,y,mn,mx); rg->update(x,y,mn,mx);
}
int query(int x) {
if (l == r) return val;
prop();
int mid = (l+r)/2;
if (x <= mid) return lf->query(x);
return rg->query(x);
}
};
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]) {
node *st = new node(0,n-1); st->build();
for (int i = 0; i < k; i++) {
if (op[i] == 1) st->update(l[i],r[i],INF,h[i]);
else st->update(l[i],r[i],h[i],-INF);
// for (int j = 0; j < n; j++) cout << st->query(j) << ' ';
// cout << '\n';
}
for (int i = 0; i < n; i++) ans[i] = st->query(i);
}
/*
10 6
1 1 8 4
0 4 9 1
0 3 6 5
1 0 5 3
1 2 2 5
0 6 7 0
*/
