#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
const int maxn = 2000010;
const int INF = INT_MAX/4;
const int mod = 1e9+7;
int ans[maxn];
struct node {
int s, m, e;
int maxv= INF, minv=0;
node *l, *r;
node (int _s, int _e) {
s = _s; e = _e; m = (s+e)/2;
if (s != e) {
l = new node(s,m);
r = new node(m+1,e);
}
}
void calc(int type, int x) {
if (type == 0) { //minimise
maxv = min(maxv, x);
minv = min(minv, x);
} else {
minv = max(minv, x);
maxv = max(maxv, x);
}
}
void push() {
// assert(s != e);
if (minv != 0 and s != e) {
l -> setmin(s, m, minv);
r -> setmin(m+1, e, minv);
minv = 0;
}
if (maxv != INF and s != e) {
l -> setmax(s, m, maxv);
r -> setmax(m+1, e, maxv);
maxv = INF;
}
}
void setmax(int x, int y, int nv) {
if (s == x and e == y) {
calc(0, nv);
} else {
push();
if (x > m) r -> setmax(x,y, nv);
else if (y <= m) l -> setmax(x,y,nv);
else l -> setmax(x,m,nv), r -> setmax(m+1,y,nv);
}
}
void setmin(int x, int y, int nv) {
if (s == x and e == y) {
calc(1, nv);
} else {
push();
if (x > m) r -> setmin(x,y, nv);
else if (y <= m) l -> setmin(x,y,nv);
else l -> setmin(x,m,nv), r -> setmin(m+1,y,nv);
}
}
void rmq() {
// cout << s << " " << e << " " << minv << " " << maxv << "\n";
if (s == e) ans[s] = minv;
else {
push();
l -> rmq();
r -> rmq();
}
}
}*root;
void buildWall(int n, int Q, int op[], int left[], int right[], int height[], int finalHeight[]){
root = new node(0,n-1);
for (int q = 0; q < Q; q++) {
int t = op[q];
int l = left[q];
int r = right[q];
int h = height[q];
if (t == 1) { //adding -> set min
root -> setmin(l,r,h);
} else {
root -> setmax(l,r,h);
}
// root -> rmq();
// for (int i = 0; i< n;i++) cout <<ans[i] << " ";
// cout << "\n";
}
root -> rmq();
for (int i =0;i<n;i++) {
finalHeight[i] = ans[i];
}
}
