#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i , j , k) for (int i = j; i < (int) k; i++)
#define lid id<<1
#define rid lid|1
const int N = 2e6 + 10;
int n2;
int segMin[N << 2];
int segMax[N << 2];
inline int smin(int &a, int b) { return b < a ? a = b : a; }
inline int smax(int &a, int b) { return a < b ? a = b : a; }
inline void applyMax(int id, int val) {
smax(segMin[id] , val);
smax(segMax[id] , val);
}
inline void applyMin(int id, int val) {
smin(segMin[id] , val);
smin(segMax[id] , val);
}
inline void shift(int id) {
applyMin(lid , segMax[id]);
applyMin(rid , segMax[id]);
applyMax(lid , segMin[id]);
applyMax(rid , segMin[id]);
segMin[id] = 0;
segMax[id] = 1e5;
}
void segApplyMin(int s, int t, int val , int l = 0 , int r = n2 , int id = 1) {
if (l >= s && r <= t) {
applyMin(id , val);
return;
}
int mid = l + r >> 1;
shift(id);
if (s < mid) segApplyMin(s ,t , val , l , mid , lid);
if (t > mid) segApplyMin(s , t , val , mid , r , rid);
}
void segApplyMax(int s, int t, int val , int l = 0 , int r = n2 , int id = 1) {
if (l >= s && r <= t) {
applyMax(id , val);
return;
}
int mid = l + r >> 1;
shift(id);
if (s < mid) segApplyMax(s ,t , val , l , mid , lid);
if (t > mid) segApplyMax(s , t , val , mid , r , rid);
}
int res[N];
void dfs(int l = 0, int r = n2, int id = 1) {
if (l == r - 1) {
res[l] = segMin[id];
// cout << l << ' '<< segMin[id] << ' '<< segMax[id] << endl;
return;
}
int mid= l +r >> 1;
shift(id);
dfs(l , mid, lid);
dfs(mid ,r, rid);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
n2 = n;
fill(segMax , segMax + (N << 2) , 1e5 + 1);
rep(i , 0 , k)
op[i] == 1 ?
segApplyMax(left[i] , right[i] + 1 , height[i]) :
segApplyMin(left[i] , right[i] + 1 , height[i]);
// cout << "DONE" << endl;
dfs();
memcpy(finalHeight , res , 4 * n2);
return;
}
