#include "wall.h"
#include<algorithm>
using namespace std;
int T[1<<22], P[1<<22], M[1<<22];
inline void update_node(int rt, int mode, int h){
if(mode == 1){
T[rt] = max(T[rt], h);
P[rt] = max(P[rt], h);
M[rt] = max(M[rt], P[rt]);
}
else{
T[rt] = min(T[rt], h);
M[rt] = min(M[rt], h);
P[rt] = min(P[rt], M[rt]);
}
}
void pushdown(int rt){
update_node(rt<<1, 2, M[rt]);
update_node(rt<<1, 1, P[rt]);
update_node(rt<<1|1, 2, M[rt]);
update_node(rt<<1|1, 1, P[rt]);
P[rt] = 0, M[rt] = 1e5 + 5;
}
void update(int rt, int s, int d, int mode, int l, int r, int h){
if(l <= s && d <= r){
update_node(rt, mode, h);
return;
}
pushdown(rt);
int m = (s+d)>>1;
if(l<=m)update(rt<<1, s, m, mode, l, r, h);
if(m<r)update(rt<<1|1, m+1, d, mode, l, r, h);
}
void get_ans(int rt, int s, int d, int &cnt, int arr[]){
if(s == d){
arr[cnt++] = T[rt];
return;
}
int m = (s+d)>>1;
pushdown(rt);
get_ans(rt<<1, s, m, cnt, arr);
get_ans(rt<<1|1, m+1, d, cnt, arr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
int i;
for(i=0;i<1<<22;i++)M[i] = 1e5 + 5;
for(i=0;i<k;i++)update(1, 0, n-1, op[i], left[i], right[i], height[i]);
int cnt = 0;
get_ans(1, 0, n-1, cnt, finalHeight);
}
