/**
* author: AgentPengin ( Độc cô cầu bại )
* created: 23.12.2022 10:08:02
* too lazy to update time
**/
#include "wall.h"
#include<bits/stdc++.h>
#define EL '\n'
#define fi first
#define se second
#define NAME "TASK"
#define ll long long
#define lcm(a,b) (a/gcd(a,b))*b
#define db(val) "["#val" = " << (val) << "] "
#define bend(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define ex exit(0)
using namespace std;
const ll mod = 1e9 + 7;
const int inf = 0x1FFFFFFF;
const int MAXN = 2e6 + 5;
int res[MAXN];
pair<int,int> st[MAXN << 2];
void pull(int id) {
st[id].fi = max(st[id << 1].fi,st[id << 1 | 1].fi);
st[id].se = min(st[id << 1].se,st[id << 1 | 1].se);
}
void getnew(int id,int val) {
st[id].fi = st[id].se = val;
}
void push(int id) {
if (st[id].fi != st[id].se) return;
getnew(id << 1,st[id].se);
getnew(id << 1 | 1,st[id].se);
}
void updateMax(int u,int v,int height,int id,int l,int r) {
if (v < l || u > r || st[id].se >= height) return;
if (u <= l && r <= v && st[id].fi <= height) {
getnew(id,height);
return;
}
push(id);
int mid = l + r >> 1;
updateMax(u,v,height,id << 1,l,mid);
updateMax(u,v,height,id << 1 | 1,mid + 1,r);
pull(id);
}
void updateMin(int u,int v,int height,int id,int l,int r) {
if (v < l || u > r || st[id].fi <= height) return;
if (u <= l && r <= v && st[id].se >= height) {
getnew(id,height);
return;
}
push(id);
int mid = l + r >> 1;
updateMin(u,v,height,id << 1,l,mid);
updateMin(u,v,height,id << 1 | 1,mid + 1,r);
pull(id);
}
void build(int id,int l,int r) {
if (l == r) {
res[l] = st[id].se;
return;
}
push(id);
int mid = l + r >> 1;
build(id << 1,l,mid);
build(id << 1 | 1,mid + 1,r);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]) {
for (int i = 0;i < k;i++) {
if (op[i] == 1) updateMax(left[i],right[i],height[i],1,0,n - 1);
else updateMin(left[i],right[i],height[i],1,0,n - 1);
}
build(1,0,n - 1);
for (int i = 0;i < n;i++) finalHeight[i] = res[i];
}
