#include "bits/stdc++.h"
using namespace std;
typedef int ll;
struct SeggsTree{
SeggsTree *l = 0, *r = 0;
int low = 0, high = 0;
struct Data{
ll mx, mn;
Data() {mx = -(INT_MAX-1), mn = INT_MAX;}
Data(ll X, ll N) {mx = X, mn = N;}
static Data merge(Data a, Data b){
return Data(max(a.mx, b.mx), min(a.mn, b.mn));
}
};
Data d;
SeggsTree(int L, int R){
low = L, high = R;
if(R - L <= 1){
d = Data(0, 0);
return;
}
int mid = low + (high - low) / 2;
l = new SeggsTree(low, mid);
r = new SeggsTree(mid, high);
d = Data::merge(l->d, r->d);
}
~SeggsTree(){
if(!l) return;
delete l;
delete r;
}
int lazy = -1;
void push(){
if(lazy == -1) return;
l->d = Data(lazy, lazy);
l->lazy = lazy;
r->d = Data(lazy, lazy);
r->lazy = lazy;
lazy = -1;
}
Data query(int L, int R){
if(R <= low || high <= L) return Data();
if(L <= low && high <= R) return d;
push();
return Data::merge(l->query(L,R), r->query(L, R));
}
void updateAdd(int L, int R, int k){
if(R <= low || high <= L || d.mn >= k) return;
if(L <= low && high <= R && d.mx <= k){
d = Data(k, k);
lazy = k;
return;
}
push();
l->updateAdd(L, R, k);
r->updateAdd(L, R, k);
d = Data::merge(l->d, r->d);
}
void updateSub(int L, int R, int k){
if(R <= low || high <= L || d.mx <= k) return;
if(L <= low && high <= R && d.mn >= k){
d = Data(k, k);
lazy = k;
return;
}
push();
l->updateSub(L, R, k);
r->updateSub(L, R, k);
d = Data::merge(l->d, r->d);
}
};
void buildWall(int n, int k, int op[], int left[], int right[],
int height[], int finalHeight[]){
SeggsTree *tree = new SeggsTree(0, n);
for(int i = 0; i < k; i++){
if(op[i] == 1) tree->updateAdd(left[i], right[i]+1, height[i]);
else tree->updateSub(left[i], right[i]+1, height[i]);
}
for(int i = 0; i < n; i++) finalHeight[i] = tree->query(i, i+1).mn;
}
