#include "wall.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pop_back
#define mp make_pair
#define bb back
#define ff first
#define ss second
using namespace std;
vector<vector<int> > segtree;
void propogate(int& indx) {
if (segtree[indx][0] != -1) {
segtree[indx*2][0] = max(segtree[indx*2][0], segtree[indx][0]);
segtree[indx*2+1][0] = max(segtree[indx*2+1][0], segtree[indx][0]);
if (segtree[indx*2][1] != -1)
segtree[indx*2][1] = max(segtree[indx*2][1], segtree[indx][0]);
if (segtree[indx*2+1][1] != -1)
segtree[indx*2+1][1] = max(segtree[indx*2+1][1], segtree[indx][0]);
segtree[indx][0] = -1;
}
if (segtree[indx][1] != -1) {
if (segtree[indx*2][1] != -1)
segtree[indx*2][1] = min(segtree[indx*2][1], segtree[indx][1]);
else
segtree[indx*2][1] = segtree[indx][1];
if (segtree[indx*2+1][1] != -1)
segtree[indx*2+1][1] = min(segtree[indx*2+1][1], segtree[indx][1]);
else
segtree[indx*2+1][1] = segtree[indx][1];
segtree[indx*2][0] = min(segtree[indx*2][0], segtree[indx][1]);
segtree[indx*2+1][0] = min(segtree[indx*2+1][0], segtree[indx][1]);
segtree[indx][1] = -1;
}
}
void update(int indx, int st, int end, int& l, int& r, int& v, int& t) {
if (st > r || end < l)
return;
if (l <= st && end <= r) {
if (t == 1) {
segtree[indx][0] = max(segtree[indx][0], v);
if (segtree[indx][1] != -1)
segtree[indx][1] = max(segtree[indx][1], v);
} else {
if (segtree[indx][1] != -1)
segtree[indx][1] = min(segtree[indx][1], v);
else
segtree[indx][1] = v;
segtree[indx][0] = min(segtree[indx][0], v);
}
return;
}
propogate(indx);
int mid = (st + end) / 2;
update(indx*2, st, mid, l, r, v, t);
update(indx*2+1, mid+1, end, l, r, v, t);
}
int query(int indx, int st, int end, int& v) {
if (st == end) {
return segtree[indx][0];
}
propogate(indx);
int mid = (st + end) / 2;
if (v <= mid)
return query(indx*2, st, mid, v);
return query(indx*2+1, mid+1, end, v);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
segtree.resize(n*3+n/2, {0, 0});
for (int i = 0; i < k; i++) {
update(1, 0, n-1, left[i], right[i], height[i], op[i]);
}
for (int i = 0; i < n; i++)
finalHeight[i] = query(1, 0, n-1, i);
return;
}
