#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
struct LazySeg {
vector<pair<int, int>> seg;
vector<pair<int, int>> lazy;
int sz;
pair<int, int> comb(pair<int, int> s1, pair<int, int> s2){
return {min(s1.first, s2.first), max(s1.second, s2.second)};
}
LazySeg(int size){
sz = size;
lazy.resize(4*sz, {0, INT_MAX});
seg.resize(4*sz, {0, INT_MAX});
}
void push(int n){
seg[n].first = min(lazy[n].second, max(seg[n].first, lazy[n].first));
seg[n].second = max(lazy[n].first, min(seg[n].second, lazy[n].second));
if(2*n+1 < 4*sz){
lazy[2*n].first = min(lazy[n].second, max(lazy[2*n].first, lazy[n].first));
lazy[2*n].second = max(lazy[n].first, min(lazy[2*n].second, lazy[n].second));
lazy[2*n+1].first = min(lazy[n].second, max(lazy[2*n+1].first, lazy[n].first));
lazy[2*n+1].second = max(lazy[n].first, min(lazy[2*n+1].second, lazy[n].second));
}
lazy[n] = {0, INT_MAX};
}
void __update(int n, int l, int r, int left, int right, int val, bool type){ // type 0 -> Add, type 1 -> Delete
push(n);
if(l > right || r < left) return;
if(l >= left && r <= right){
if(type){
lazy[n].second = val;
}
else{
lazy[n].first = val;
}
push(n);
return;
}
int m = (l+r)/2;
__update(2*n, l, m, left, right, val, type);
__update(2*n+1, m+1, r, left, right, val, type);
}
void update(int left, int right, int val, bool type) { __update(1, 1, sz, left, right, val, type); }
void answer(int n, int l, int r, int ans[]){
push(n);
if(l == r){
ans[l-1] = seg[n].first;
return;
}
int m = (l+r)/2;
answer(2*n, l, m, ans);
answer(2*n+1, m+1, r, ans);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
LazySeg seg(n);
for(int i=0;i<k;i++){
seg.update(left[i]+1, right[i]+1, height[i], op[i]-1);
}
seg.answer(1, 1, n, finalHeight);
}
