#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
struct ops {
int mn, mx;
ops(int x = INF, int y = -INF): mn(x), mx(y) {}
ops operator + (ops v) {
if (mn < v.mx) return ops(v.mx,v.mx);
if (mx > v.mn) return ops(v.mn,v.mn);
return ops(min(mn,v.mn),max(mx,v.mx));
}
};
struct segTree {
segTree *lf, *rg;
int l, r;
ops val;
segTree(int x, int y) {
l = x, r = y;
val = ops(0,0);
}
void build() {
if (l == r) return;
int mid = (l+r)/2;
lf = new segTree(l,mid); lf->build();
rg = new segTree(mid+1,r); rg->build();
}
void prop() {
lf->val = lf->val+val;
rg->val = rg->val+val;
val = ops();
}
void update(int x, int y, ops v) {
if (l > y || r < x) return;
if (l >= x && r <= y) {
val = val+v;
return;
}
prop();
lf->update(x,y,v); rg->update(x,y,v);
}
void solve(int ans[]) {
if (l == r) {
ans[l] = val.mn;
return;
}
prop();
lf->solve(ans); rg->solve(ans);
}
} *st;
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]) {
st = new segTree(0,n-1); st->build();
for (int i = 0; i < k; i++) {
if (op[i] == 1) st->update(l[i],r[i],ops(INF,h[i]));
else st->update(l[i],r[i],ops(h[i],-INF));
// st->solve(ans);
// for (int j = 0; j < n; j++) cout << ans[j] << ' ';
// cout << '\n';
}
st->solve(ans);
}
/*
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
*/
