#include "wall.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int NMAX = 2e6;
const int INF = 2e9;
struct LazyNode {
int mini, maxi;
LazyNode() : mini(0), maxi(INF) {}
LazyNode(int mini, int maxi) : mini(mini), maxi(maxi) {}
};
struct AINT {
LazyNode lazy[4 * NMAX + 1];
void Apply(int node, int left, int right, LazyNode parent_lazy) {
lazy[node].mini = max(lazy[node].mini, parent_lazy.mini);
lazy[node].maxi = max(lazy[node].maxi, lazy[node].mini);
lazy[node].maxi = min(lazy[node].maxi, parent_lazy.maxi);
lazy[node].mini = min(lazy[node].mini, lazy[node].maxi);
}
void Push(int node, int left, int right) {
int mid = (left + right) / 2;
Apply(node * 2, left, mid, lazy[node]);
Apply(node * 2 + 1, mid + 1, right, lazy[node]);
lazy[node] = LazyNode();
}
void Update(int node, int left, int right, int Uleft, int Uright, LazyNode value) {
if(left > Uright || right < Uleft) {
return;
}
if(left >= Uleft && right <= Uright) {
Apply(node, left, right, value);
return;
}
Push(node, left, right);
int mid = (left + right) / 2;
Update(node * 2, left, mid, Uleft, Uright, value);
Update(node * 2 + 1, mid + 1, right, Uleft, Uright, value);
}
void Print(int node, int left, int right, int* a) {
if(left == right) {
a[left] = lazy[node].mini;
return;
}
Push(node, left, right);
int mid = (left + right) / 2;
Print(node * 2, left, mid, a);
Print(node * 2 + 1, mid + 1, right, a);
}
}aint;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
for(int i = 0; i < k; i++) {
int type = op[i];
int l = left[i]; l++;
int r = right[i]; r++;
int value = height[i];
if(type == 1) { // Maximize
aint.Update(1, 1, n, l, r, LazyNode(value, INF));
}
else {
aint.Update(1, 1, n, l, r, LazyNode(0, value));
}
}
aint.Print(1, 1, n, finalHeight);
}
