#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'
struct Node {
ll max, min;
};
class SegmentTree {
private:
vector<Node> tree; vector<ll> raw; int n;
vector<bool> marked;
Node bound = {(ll) 1e6, 0};
Node resolve(Node p, Node c) {
if (p.min >= c.max) return {p.min, p.min};
if (p.max <= c.min) return {p.max, p.max};
return {min(p.max, c.max), max(p.min, c.min)};
}
void push(int p) {
marked[p] = false;
int c1 = 2*p+1, c2 = 2*p+2;
marked[c1] = marked[c2] = true;
tree[c1] = resolve(tree[p], tree[c1]);
tree[c2] = resolve(tree[p], tree[c2]);
tree[p] = bound;
}
// t: 0 -> increase to val, 1 -> decrease to val
void update(int i, int j, ll k, int t, int l, int r, int p) {
if (l > j or r < i) return;
if (l >= i and r <= j) {
marked[p] = true;
if (t == 0) tree[p] = {max(tree[p].max, k), max(tree[p].min, k)};
else tree[p] = {min(tree[p].max, k), min(tree[p].min, k)};
return;
}
int mid = (l + r) / 2;
if (marked[p]) push(p);
int c1 = 2*p+1, c2 = 2*p+2;
update(i, j, k, t, l, mid, c1); update(i, j, k, t, mid+1, r, c2);
}
public:
SegmentTree(vector<ll> input) {
raw = input;
n = raw.size();
marked.resize(4*n);
tree.resize(4*n, bound);
}
void update(int i, int j, int val, int t) {
update(i, j, val, t, 0, n-1, 0);
}
void answer(int l, int r, int p, int ans[]) {
if (l == r) {
ans[l] = raw[l];
//if (l == 0) cout << tree[p].max << " " << tree[p].min << endl;
if (raw[l] > tree[p].max) ans[l] = tree[p].max;
if (raw[l] < tree[p].min) ans[l] = tree[p].min;
return;
}
int mid = (l + r) / 2;
if (marked[p]) push(p);
int c1 = 2*p+1, c2 = 2*p+2;
answer(l, mid, c1, ans); answer(mid+1, r, c2, ans);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
vector<ll> nums(n);
SegmentTree tree(nums);
for_(i, 0, k) tree.update(left[i], right[i], height[i], op[i]-1);
tree.answer(0, n-1, 0, finalHeight);
}
//int main() {
//#ifndef ONLINE_JUDGE
//freopen("test.in", "r", stdin);
//#endif
//ios_base::sync_with_stdio(false);
//cin.tie(0);
//int n = 10, k = 6;
//int op[] = {1, 2, 2, 1, 1, 2};
//int left[] = {1, 4, 3, 0, 2, 6};
//int right[] = {8, 9, 6, 5, 2, 7};
//int height[] = {4, 1, 5, 3, 5, 0};
//int* finalHeight = (int*)calloc(sizeof(int), n);
//buildWall(10, k, op, left, right, height, finalHeight);
//for_(i, 0, n) cout << finalHeight[i] << " ";
//cout << endl;
//return 0;
//}
