#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
struct SegmentTree
{
int n;
vector<int>seg;
vector<pair<int, int>>lazy;
SegmentTree(int _n) {
n = _n;
seg.resize(4 * n + 5, 0);
lazy.resize(4 * n + 5, { 1e9 + 7,-1 });
}
void push(int x, int lx, int rx) {
if (lx == rx)
return;
if (lazy[x].first != 1e9) {
seg[2 * x] = min(seg[2 * x], lazy[x].first);
lazy[2 * x].first = min(lazy[2 * x].first, lazy[x].first);
lazy[2 * x].second = min(lazy[2 * x].second, lazy[x].first);
seg[2 * x + 1] = min(seg[2 * x + 1], lazy[x].first);
lazy[2 * x + 1].first = min(lazy[2 * x + 1].first, lazy[x].first);
lazy[2 * x + 1].second = min(lazy[2 * x + 1].second, lazy[x].first);
}
if (lazy[x].second != -1) {
seg[2 * x] = max(seg[2 * x], lazy[x].second);
lazy[2 * x].first = max(lazy[2 * x].first, lazy[x].second);
lazy[2 * x].second = max(lazy[2 * x].second, lazy[x].second);
seg[2 * x + 1] = max(seg[2 * x + 1], lazy[x].second);
lazy[2 * x + 1].first = max(lazy[2 * x + 1].first, lazy[x].second);
lazy[2 * x + 1].second = max(lazy[2 * x + 1].second, lazy[x].second);
}
lazy[x] = { 1e9,-1 };
}
void update(int x, int lx, int rx, int l, int r, int type, int v) {
push(x, lx, rx);
if (lx > rx || l > rx || lx > r)
return;
if (lx >= l && rx <= r) {
if (type == 1)
seg[x] = max(seg[x], v), lazy[x].first = max(lazy[x].first, v), lazy[x].second = max(lazy[x].second, v);
else
seg[x] = min(seg[x], v), lazy[x].first = min(lazy[x].first, v), lazy[x].second = min(lazy[x].second, v);
//push(x, lx, rx);
return;
}
int mid = (lx + rx) / 2;
update(2 * x, lx, mid, l, r, type, v);
update(2 * x + 1, mid + 1, rx, l, r, type, v);
}
int get(int x, int lx, int rx, int i) {
if (lx == rx)
return seg[x];
push(x, lx, rx);
int mid = (lx + rx) / 2;
if (i <= mid)
return get(2 * x, lx, mid, i);
else
return get(2 * x + 1, mid + 1, rx, i);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
for (int i = 0; i < n; i++)
finalHeight[i] = 0;
SegmentTree seg(n);
for (int i = 0; i < k; i++)
seg.update(1, 0, n - 1, left[i], right[i], op[i], height[i]);
for (int i = 0; i < n; i++)
finalHeight[i] = seg.get(1, 0, n - 1, i);
}
