#include <bits/stdc++.h>
#include "wall.h"
#define ii pair<int, int>
using namespace std;
int t[2000002 << 2][2], lazy[2000002 << 2][2]; // lower, upper
void push(int v){
// Do something
if(lazy[v][0] == 0 && lazy[v][1] == INT_MAX) return;
t[v * 2][0] = max(t[v * 2][0], lazy[v][0]);
t[v * 2 + 1][0] = max(t[v * 2 + 1][0], lazy[v][0]);
t[v * 2][1] = max(t[v * 2][1], lazy[v][0]);
t[v * 2 + 1][1] = max(t[v * 2 + 1][1], lazy[v][0]);
lazy[v * 2][0] = max(lazy[v * 2][0], lazy[v][0]);
lazy[v * 2 + 1][0] = max(lazy[v * 2 + 1][0], lazy[v][0]);
lazy[v * 2][1] = max(lazy[v * 2][1], lazy[v][0]);
lazy[v * 2 + 1][1] = max(lazy[v * 2 + 1][1], lazy[v][0]);
t[v * 2][0] = min(t[v * 2][0], lazy[v][1]);
t[v * 2 + 1][0] = min(t[v * 2 + 1][0], lazy[v][1]);
t[v * 2][1] = min(t[v * 2][1], lazy[v][1]);
t[v * 2 + 1][1] = min(t[v * 2 + 1][1], lazy[v][1]);
lazy[v * 2][0] = min(lazy[v * 2][0], lazy[v][1]);
lazy[v * 2 + 1][0] = min(lazy[v * 2 + 1][0], lazy[v][1]);
lazy[v * 2][1] = min(lazy[v * 2][1], lazy[v][1]);
lazy[v * 2 + 1][1] = min(lazy[v * 2 + 1][1], lazy[v][1]);
lazy[v][0] = 0; lazy[v][1] = INT_MAX;
}
void ins(int v, int tl, int tr, int l, int r, int type, int val){
if(l > r) return;
if(tl == l && tr == r){
if(type == 1){
// shift lower
t[v][0] = max(t[v][0], val);
t[v][1] = max(t[v][1], val);
lazy[v][0] = max(lazy[v][0], val);
lazy[v][1] = max(lazy[v][1], val);
}
else{
// shift upper;
t[v][0] = min(t[v][0], val);
t[v][1] = min(t[v][1], val);
lazy[v][0] = min(lazy[v][0], val);
lazy[v][1] = min(lazy[v][1], val);
}
return;
}
push(v);
int tm = (tl + tr) >> 1;
ins(v * 2, tl, tm, l, min(r, tm), type, val);
ins(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, type, val);
t[v][0] = min(t[v * 2][0], t[v * 2 + 1][0]);
t[v][1] = max(t[v * 2][1], t[v * 2 + 1][1]);
}
int query(int v, int tl, int tr, int pos){
if(tl == pos && tr == pos) return t[v][0];
push(v);
int tm = (tl + tr) >> 1;
if(pos <= tm) return query(v * 2, tl, tm, pos);
else return query(v * 2 + 1, tm + 1, tr, pos);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i = 0; i <= n << 2; i++) lazy[i][1] = INT_MAX;
for(int i = 0; i < k; i++){
ins(1, 0, n - 1, left[i], right[i], op[i], height[i]);
}
for(int i = 0; i < n; i++){
finalHeight[i] = query(1, 0, n - 1, i);
}
return;
}
