#include "wall.h"
#include <utility>
#include <algorithm>
#define ll long long
#define X first
#define Y second
#define MP make_pair
using namespace std;
const int N = 2e6 + 12;
const int INF = 1e6;
pair<int, int> t[N * 4], tt[N * 4];
int fin[N];
pair<int, int> merge(pair<int, int> x, pair<int, int> y){
if(y == MP(0, INF))
return x;
if(y.Y <= x.X)
return MP(x.X, x.X);
if(x.Y <= y.X)
return MP(x.Y, x.Y);
if(x.X <= y.X && y.X <= x.Y)
x.X = y.X;
if(x.X <= y.Y && y.Y <= x.Y)
x.Y = y.Y;
return x;
}
void push(int v){
if(tt[v] == MP(0, INF))
return;
t[v * 2] = merge(tt[v], t[v * 2]);
tt[v * 2] = merge(tt[v], tt[v * 2]);
t[v * 2 + 1] = merge(tt[v], t[v * 2 + 1]);
tt[v * 2 + 1] = merge(tt[v], tt[v * 2 + 1]);
tt[v] = MP(0, INF);
}
void upd(int v, int tl, int tr, int l, int r, pair<int, int> val){
if(tl > r || l > tr)
return;
if(tl >= l && tr <= r){
tt[v] = merge(val, tt[v]), t[v] = merge(val, t[v]);
return;
}
push(v);
int tm = (tl + tr) / 2;
upd(v * 2, tl, tm, l, r, val);
upd(v * 2 + 1, tm + 1, tr, l, r, val);
}
void solve(int v, int tl, int tr){
if(tl == tr){
fin[tl] = t[v].X;
return;
}
push(v);
int tm = (tl + tr) / 2;
solve(v * 2, tl, tm), solve(v * 2 + 1, tm + 1, tr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i = 1;i <= n * 4;i++)
tt[i] = MP(0, INF);
for(int i = 0;i < k;i++){
if(op[i] == 1){
upd(1, 1, n, left[i] + 1, right[i] + 1, MP(height[i], INF));
}
else{
upd(1, 1, n, left[i] + 1, right[i] + 1, MP(0, height[i]));
}
}
solve(1, 1, n);
for(int i = 1;i <= n;i++)
finalHeight[i - 1] = fin[i];
}
