#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2000101;
struct Node{
int min_op;
int max_op;
};
Node Tree[N * 3];
void init(int node, int cl, int cr){
Tree[node].min_op = (int)1e9 + 9;
Tree[node].max_op = 0;
if(cl == cr){
return;
}
int md = (cl + cr)/2;
init(node * 2, cl, md);
init(node * 2 + 1, md + 1, cr);
}
void maxi(int node, int x){ // apply max(node)
Tree[node].max_op = max(Tree[node].max_op, x);
Tree[node].min_op = max(Tree[node].min_op, Tree[node].max_op);
}
void mini(int node, int x){ // apply min(node)
Tree[node].min_op = min(Tree[node].min_op, x);
Tree[node].max_op = min(Tree[node].max_op, Tree[node].min_op);
}
void push(int node, int tl, int tr){
mini(node * 2, Tree[node].min_op);
mini(node * 2 + 1, Tree[node].min_op);
maxi(node * 2, Tree[node].max_op);
maxi(node * 2 + 1, Tree[node].max_op);
Tree[node].max_op = 0;
Tree[node].min_op = (int)1e9 + 9;
}
void update(int node, int cl, int cr, int tl, int tr, int x, int op){
if(cr < tl)
return;
if(cl > tr)
return;
if(cl >= tl and cr <= tr){
if(op == 1)
maxi(node, x);
else
mini(node, x);
return;
}
push(node, cl, cr);
int md = (cl + cr)/2;
update(node*2, cl, md, tl, tr, x, op);
update(node*2+1, md + 1, cr, tl, tr, x, op);
}
int fin[N];
void ff(int node, int cl, int cr){
if(cl == cr){
fin[cl] = Tree[node].max_op;
return;
}
push(node, cl, cr);
int md = (cl + cr)/2;
ff(node * 2, cl, md);
ff(node * 2 + 1, md + 1, cr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
init(1, 0, n-1);
for(int i = 0;i < k;i ++ ){
update(1, 0, n - 1, left[i], right[i], height[i], op[i]);
}
ff(1, 0, n - 1);
for(int i = 0;i < n;i ++ )
finalHeight[i] = fin[i];
return;
}
