#include "wall.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define lc id<<1
#define rc id<<1^1
#define nmax 2000008
const int inf = 1e6;
using namespace std;
typedef pair<int, int> pii;
pii operator+(pii x, int y){
return (x.fi < y) ? make_pair(y, x.fi) : ((x.fi > y && y > x.se) ? make_pair(x.fi, y) : x);
}
pii operator-(pii x, int y){
return (x.fi > y) ? make_pair(y, x.fi) : ((x.fi < y && y < x.se) ? make_pair(x.fi, y) : x);
}
pii operator+(pii x, pii y){
return (x + y.fi) + y.se;
}
pii operator-(pii x, pii y){
return (x - y.fi) - y.se;
}
int N, ans[nmax];
struct segmenttrebeats{
pii mi[nmax << 2], ma[nmax << 2];
int lazi[nmax << 2];
void build(int id = 1, int l = 0, int r = N - 1){
lazi[id] = -1;
if (l == r){
mi[id] = {0, inf};
ma[id] = {0, -inf};
return;
}
int mid = (l + r) >> 1;
build(lc, l, mid);
build(rc, mid + 1, r);
mi[id] = mi[lc] - mi[rc];
ma[id] = ma[lc] + ma[rc];
}
void down(int id){
mi[lc] = mi[rc] = {lazi[id], inf};
ma[lc] = ma[rc] = {lazi[id], -inf};
lazi[lc] = lazi[rc] = lazi[id];
lazi[id] = -1;
return;
}
void upd_max(int u, int v, int k, int id = 1, int l = 0, int r = N - 1){
if (r < u || l > v || mi[id].fi >= k)
return;
if ((u <= l && r <= v) && (ma[id].fi <= k || mi[id].se == inf)){
mi[id] = {k, inf};
ma[id] = {k, -inf};
lazi[id] = k;
return;
}
int mid = (l + r) >> 1;
if (lazi[id] != -1)
down(id);
upd_max(u, v, k, lc, l, mid);
upd_max(u, v, k, rc, mid + 1, r);
mi[id] = mi[lc] - mi[rc];
ma[id] = ma[lc] + ma[rc];
}
void upd_min(int u, int v, int k, int id = 1, int l = 0, int r = N - 1){
if (r < u || l > v || k >= ma[id].fi)
return;
if ((u <= l && r <= v) && (mi[id].fi >= k || ma[id].se == -inf)){
mi[id] = {k, inf};
ma[id] = {k, -inf};
lazi[id] = k;
return;
}
int mid = (l + r) >> 1;
if (lazi[id] != -1)
down(id);
upd_min(u, v, k, lc, l, mid);
upd_min(u, v, k, rc, mid + 1, r);
mi[id] = mi[lc] - mi[rc];
ma[id] = ma[lc] + ma[rc];
}
void dfs(int id = 1, int l = 0, int r = N - 1){
if (l == r){
ans[l] = mi[id].fi;
return;
}
int mid = (l + r) >> 1;
if (lazi[id] != -1)
down(id);
dfs(lc, l, mid);
dfs(rc, mid + 1, r);
}
}tree;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
N = n;
tree.build();
for (int i = 0; i < k; i++){
if (op[i] == 1)
tree.upd_max(left[i], right[i], height[i]);
else
tree.upd_min(left[i], right[i], height[i]);
}
tree.dfs();
for (int i = 0; i < n; i++)
finalHeight[i] = ans[i];
}
