#include <bits/stdc++.h>
using namespace std;
#include "wall.h"
const int INF = 1e9;
const int nax = 2e6 + 3;
pair<int, int>st[nax * 4];
void propagate(int v) {
for(int c : {v*2, v*2+1}) {
st[c].first = max(st[v].first, st[c].first);
st[c].second = max(st[c].first, st[c].second);
st[c].second = min(st[c].second, st[v].second);
st[c].first = min(st[c].first, st[c].second);
}
st[v] = {-INF, INF};
}
void maximize(int l, int r, int L, int R, int val, int v) {
if(l>R || r<L) return;
if(l>=L && r<=R) {
st[v].first = max(st[v].first, val);
st[v].second = max(st[v].first, st[v].second);
return;
}
propagate(v);
int mid = (l+r)/2;
maximize(l, mid, L, R, val, v*2);
maximize(mid+1, r, L, R, val, v*2+1);
}
void minimize(int l, int r, int L, int R, int val, int v) {
if(l>R || r<L) return;
if(l>=L && r<=R) {
st[v].second = min(st[v].second, val);
st[v].first = min(st[v].first, st[v].second);
return;
}
propagate(v);
int mid = (l+r)/2;
minimize(l, mid, L, R, val, v*2);
minimize(mid+1, r, L, R, val, v*2+1);
}
int query(int l, int r, int p, int v) {
if(l==r) {
return min(max(0, st[v].first), st[v].second);
}
propagate(v);
int mid = (l+r)/2;
if(p<=mid) return query(l, mid, p, v*2);
else return query(mid+1, r, p, v*2+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=1; i<nax * 4; ++i) {
st[i] = {-INF, INF};
}
for(int i=0; i<k; ++i) {
if(op[i]==1) {
maximize(1, n, left[i]+1, right[i]+1, height[i], 1);
} else {
minimize(1, n, left[i]+1, right[i]+1, height[i], 1);
}
}
for(int i=0; i<n; ++i) {
finalHeight[i] = query(1, n, i+1, 1);
}
return;
}
