/**
* Author: Lưu Diệp Thành (Save Diệp Thành)
* Le Hong Phong High School for the Gifted (i2528)
**/
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define ll long long
#define ushort unsigned short
#define FOR(i,l,r) for(int i = (l), _r = (r); i <= _r; i++)
#define FORN(i,r,l) for(int i = (r), _l = (l); i >= _l; i--)
#define endl '\n'
#define sz(x) (int)x.size()
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define MASK(x) (1LL << (x))
#define BIT(x,i) (((x) >> (i)) & 1)
#define ins insert
#define segleft (id<<1)
#define segright (id<<1|1)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
const int MOD = 1e9+7;
struct Node {
int minvalue = 0, maxvalue = INT_MAX;
};
struct SegmentTree {
private:
vector<Node> st;
int n;
// minvalue <= maxvalue
void apply(int id, Node x) {
st[id].minvalue = max(st[id].minvalue, x.minvalue);
st[id].maxvalue = max(st[id].minvalue, st[id].maxvalue);
st[id].maxvalue = min(st[id].maxvalue, x.maxvalue);
st[id].minvalue = min(st[id].minvalue, st[id].maxvalue);
}
void push(int id) {
apply(segleft, st[id]);
apply(segright, st[id]);
st[id] = Node();
}
void update(int id, int l, int r, int u, int v, Node &x) {
if (l > v || r < u) return;
if (l >= u && r <= v) {
apply(id, x);
return;
}
push(id);
int mid = l+r>>1;
update(segleft, l, mid, u, v, x);
update(segright, mid+1, r, u, v, x);
}
int get(int id, int l, int r, int index) {
if (l==r) return st[id].minvalue;
push(id);
int mid = l+r>>1;
if (index <= mid) {
return get(segleft, l, mid, index);
} else {
return get(segright, mid+1, r, index);
}
}
public:
SegmentTree(int _n) {
n = _n;
st.assign(4*n+4, Node());
}
void updateRange(int l, int r, Node x) {
update(1, 0, n-1, l, r, x);
}
int getIdx(int index) {
return get(1, 0, n-1, index);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
SegmentTree tree(n);
FOR(i, 0, k-1) {
if (op[i]) {
tree.updateRange(left[i], right[i], {height[i], INT_MAX});
} else {
tree.updateRange(left[i], right[i], {0, height[i]});
}
}
FOR(i, 0, n-1) {
finalHeight[i] = tree.getIdx(i);
}
}
