#include "wall.h"
#include <bits/stdc++.h>
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
const int inf = 1e9 + 7;
const int N = 2e6 + 5;
struct node {
int mn, mx;
node(int _mn = 0, int _mx = inf) {
mn = _mn;
mx = _mx;
}
node operator + (const node& o) const {
node res;
res.mn = max(mn, o.mn);
res.mx = max(res.mn, mx);
res.mx = min(res.mx, o.mx);
res.mn = min(res.mx, res.mn);
return res;
}
} it[N << 2], lazy[N << 2];
void upd(int k, node val){
it[k] = it[k] + val;
lazy[k] = lazy[k] + val;
}
void shift(int k) {
upd(k << 1, lazy[k]);
upd(k << 1 | 1, lazy[k]);
lazy[k] = node();
}
void update(int k, int l, int r, int u, int v, node val) {
if(l > v || r < u) return;
if(u <= l && r <= v) {
upd(k, val);
return;
}
shift(k);
int mid = l + r >> 1;
update(k << 1, l, mid, u, v, val);
update(k << 1 | 1, mid + 1, r, u, v, val);
}
void get(int k, int l, int r, int *res) {
if(l == r) {
res[l - 1] = it[k].mn;
return;
}
shift(k);
int mid = l + r >> 1;
get(k << 1, l, mid, res);
get(k << 1 | 1, mid + 1, r, res);
}
void buildWall(int n, int k, int op[], int L[], int R[], int H[], int res[]) {
for(int i = 0; i < k; ++i) {
if(op[i] == 1) {
update(1, 1, n, L[i] + 1, R[i] + 1, node(H[i], inf));
} else {
update(1, 1, n, L[i] + 1, R[i] + 1, node(0, H[i]));
}
}
get(1, 1, n, res);
}
