#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
int n;
vector<int> add[30];
vector<int> rem[30];
int l,r;
int h, type;
int level,zereg[30];
void build_tree(){
zereg[0] = 1;
for(int i = 0; i <= 30; i++){
if(zereg[i] >= n){
level = i;
break;
}
zereg[i + 1] = zereg[i] * 2;
}
for(int i = 0; i <= level; i++){
for(int j = 0; j < zereg[i]; j++){
add[i].pb(-1);
rem[i].pb(-1);
}
}
}
void propogate(int k, int x){
if(rem[k][x] != -1){
add[k + 1][x * 2] = min(add[k + 1][x * 2], rem[k][x]);
add[k + 1][x * 2 + 1] = min(add[k + 1][x * 2 +1], rem[k][x]);
//
if(rem[k + 1][x * 2] != -1) rem[k + 1][x * 2] = min(rem[k + 1][x * 2], rem[k][x]);
else rem[k + 1][x * 2] = rem[k][x];
//
if(rem[k + 1][x * 2 + 1] != -1) rem[k + 1][x * 2 + 1] = min(rem[k + 1][x * 2 + 1], rem[k][x]);
else rem[k + 1][x * 2 + 1] = rem[k][x];
}
add[k + 1][x * 2]= max(add[k + 1][x * 2], add[k][x]);
add[k + 1][x * 2 + 1]= max(add[k + 1][x * 2 + 1], add[k][x]);
add[k][x] = -1;
rem[k][x] = -1;
}
void dfs(int k, int x){
int y = zereg[level - k] * x;
int z = zereg[level - k] * (x + 1) -1;;
if(l <= y && z <= r){
if(type == 1){
if(add[k][x] < h) {
add[k][x] = h;
}
}
else{
if(add[k][x] > h){
add[k][x] = h;
}
if(rem[k][x] == -1) rem[k][x] = h;
else if(rem[k][x] > h) rem[k][x] = h;
}
return;
}
if(z < l || y > r || k == level) return;
propogate(k,x);
dfs(k + 1, x * 2);
dfs(k + 1, x * 2 + 1);
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
n = N;
build_tree();
for(int i = 0; i < k; i++){
l = left[i];
r = right[i];
h = height[i];
type = op[i];
dfs(0,0);
}
for(int i = 0; i < n; i++){
int pos = i;
for(int j = level; j >= 0; j--){
if(rem[j][pos] != -1) finalHeight[i] = min(finalHeight[i], rem[j][pos]);
finalHeight[i] = max(finalHeight[i], add[j][pos]);
pos /= 2;
}
}
return;
}
