#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2097152;
const int Inf = 100000;
int sL[N << 1], sR[N << 1];
void Apply(int id, int lq, int rq){
sL[id] = max(min(sL[id], rq), lq);
sR[id] = max(min(sR[id], rq), lq);
}
void Shift(int id){
Apply(id << 1, sL[id], sR[id]);
Apply(id << 1 | 1, sL[id], sR[id]);
sL[id] = 0;
sR[id] = Inf;
}
void Query(int id, int l, int r, int lq, int rq, int L, int R){
if(r <= L || R <= l) return ;
if(l <= L && R <= r){
Apply(id, lq, rq);
return ;
}
Shift(id);
int mid = (L + R) >> 1;
Query(id << 1, l, r, lq, rq, L, mid);
Query(id << 1 | 1, l, r, lq, rq, mid, R);
}
int ans[N];
void DFS(int id, int L, int R){
if(L + 1 == R){
//cerr << "# " << L << " ! " << sL[id] << ' ' << sR[id] << '\n';
ans[L] = sL[id];
return ;
}
int mid = (L + R) >> 1;
Shift(id);
DFS(id << 1, L, mid);
DFS(id << 1 | 1, mid, R);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
fill(sR, sR + N*2, Inf);
for(int i = 0; i < k; i++){
Query(1, left[i], right[i] + 1, op[i] == 1 ? height[i] : 0, op[i] == 2 ? height[i] : Inf, 0, n);
}
DFS(1, 0, n);
for(int i = 0; i < n; i++) finalHeight[i] = ans[i];
return;
}
