#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e6 + 12;
const int INF = 1e9 + 12;
struct node {
int mn, mx;
}st[4*mxN];
int n;
void build(int i = 1, int l2 = 0, int r2 = n-1) {
st[i].mn = INF;
st[i].mx = -INF;
if(l2 == r2) {
return;
}
int m2 = (l2 + 2) / 2;
build(2*i, l2, m2);
build(2*i+1, m2+1, 2);
}
inline void assignMin(int i, int x) {
st[i].mn = min(st[i].mn, x);
st[i].mx = min(st[i].mx, x);
}
inline void assignMax(int i, int x) {
st[i].mn = max(st[i].mn, x);
st[i].mx = max(st[i].mx, x);
}
inline void push(int i) {
assignMin(2*i, st[i].mn);
assignMax(2*i, st[i].mx);
assignMin(2*i+1, st[i].mn);
assignMax(2*i+1, st[i].mx);
st[i].mn = INF;
st[i].mx = -INF;
}
void minimum(int l1, int r1, int x, int i = 1, int l2 = 0, int r2 = n-1) {
if(l1 <= l2 && r2 <= r1) {
assignMin(i, x);
return;
}
push(i);
int m2 = (l2 + r2) / 2;
if(l1 <= m2) minimum(l1, r1, x, 2*i, l2, m2);
if(m2 < r1) minimum(l1, r1, x, 2*i+1, m2+1, r2);
}
void maximum(int l1, int r1, int x, int i = 1, int l2 = 0, int r2 = n-1) {
if(l1 <= l2 && r2 <= r1) {
assignMax(i, x);
return;
}
push(i);
int m2 = (l2 + r2) / 2;
if(l1 <= m2) maximum(l1, r1, x, 2*i, l2, m2);
if(m2 < r1) maximum(l1, r1, x, 2*i+1, m2+1, r2);
}
int query(int l1, int i = 1, int l2 = 0, int r2 = n-1) {
if(l2 == r2) {
assert(st[i].mn == st[i].mx);
return st[i].mn;
}
push(i);
int m2 = (l2 + r2) / 2;
if(l1 <= m2) return query(l1, 2*i, l2, m2);
else return query(l1, 2*i+1, m2+1, r2);
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
n = N;
//for(int i = 0; i < n; ++i) {
//cerr << 0 << " ";
//}
cerr << endl;
for(int i = 0; i < k; ++i) {
if(op[i] == 1) {
maximum(left[i], right[i], height[i]);
} else {
minimum(left[i], right[i], height[i]);
}
//for(int i = 0; i < n; ++i) {
//cerr << query(i) << " ";
//}
//cerr << endl;
}
for(int i = 0; i < n; ++i) {
finalHeight[i] = query(i);
}
}
