#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int MAXN = 2e6 + 10;
struct node{
int Min, Max;
} a[4*MAXN];
void update(int l,int r,int constl,int constr,int idx,int val,string type){
if(l<=constl && constr<=r){
if(type == "ADD"){
a[idx].Min = max(a[idx].Min, val);
a[idx].Max = max(a[idx].Max, val);
}
else{
a[idx].Min = min(a[idx].Min, val);
a[idx].Max = min(a[idx].Max, val);
}
return;
}
int mid = (constl+constr)/2;
//Lazy propagation: Remember to return a[idx].Min and a[idx].Max into initial state
a[2*idx+1].Min = max(a[2*idx+1].Min, a[idx].Max);
a[2*idx+1].Max = max(a[2*idx+1].Max, a[idx].Max);
a[2*idx+2].Min = max(a[2*idx+2].Min, a[idx].Max);
a[2*idx+2].Max = max(a[2*idx+2].Max, a[idx].Max);
a[2*idx+1].Min = min(a[2*idx+1].Min, a[idx].Min);
a[2*idx+1].Max = min(a[2*idx+1].Max, a[idx].Min);
a[2*idx+2].Min = min(a[2*idx+2].Min, a[idx].Min);
a[2*idx+2].Max = min(a[2*idx+2].Max, a[idx].Min);
a[idx].Min = 1e9;
a[idx].Max = 0;
if(mid<l || r<constl) update(l, r, mid+1, constr, 2*idx+2, val, type);
else if(constr<l || r<mid+1) update(l, r, constl, mid, 2*idx+1, val, type);
else{
update(l, r, constl, mid, 2*idx+1, val, type);
update(l, r, mid+1, constr, 2*idx+2, val, type);
}
}
int N;
vector<int> ans;
void query(int l,int r,int idx){
if(l == r){
if(l >= 1 && r <= N) ans.push_back(a[idx].Max);
return;
}
//Lazy propagation during query too
a[2*idx+1].Min = max(a[2*idx+1].Min, a[idx].Max);
a[2*idx+1].Max = max(a[2*idx+1].Max, a[idx].Max);
a[2*idx+2].Min = max(a[2*idx+2].Min, a[idx].Max);
a[2*idx+2].Max = max(a[2*idx+2].Max, a[idx].Max);
a[2*idx+1].Min = min(a[2*idx+1].Min, a[idx].Min);
a[2*idx+1].Max = min(a[2*idx+1].Max, a[idx].Min);
a[2*idx+2].Min = min(a[2*idx+2].Min, a[idx].Min);
a[2*idx+2].Max = min(a[2*idx+2].Max, a[idx].Min);
a[idx].Min = 1e9;
a[idx].Max = 0;
int mid = (l+r) / 2;
query(l, mid, 2*idx+1);
query(mid+1, r, 2*idx+2);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
N = n;
//initialize all Min's to 1e9
for(int i=0; i<MAXN; i++){
a[i].Min = 1e9;
a[i].Max = 0;
}
for(int i=0; i<k; i++){
int ops = op[i];
int L, R, h;
L = left[i], R = right[i], h = height[i];
L++; R++;
if(ops == 1){
update(L, R, 0, MAXN-1, 0, h, "ADD");
}
else{
update(L, R, 0, MAXN-1, 0, h, "REM");
}
}
query(0, MAXN-1, 0);
for(int i=0; i<N; i++) finalHeight[i] = ans[i];
}
