/*
Zadanie: Wall
Autor: Tomasz Kwiatkowski
*/
#include <bits/stdc++.h>
#include "wall.h"
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
struct segTree {
vector<pair<int, int>> t_min;
vector<pair<int, int>> lazy;
vector<pair<int, int>> t_max;
int BASE;
segTree(int n)
{
BASE = 1;
while (BASE <= n)
BASE *= 2;
t_min.resize(2*BASE + 7, {1e9, 0});
t_max.resize(2*BASE + 7, {0, 0});
lazy.resize(2*BASE + 7, {-1, 0});
for (int i = 0; i < BASE; ++i)
t_min[BASE + i] = t_max[BASE + i] = {0, i};
for (int i = BASE - 1; i > 0; --i) {
t_min[i] = min(t_min[2*i], t_min[2*i + 1]);
t_max[i] = max(t_max[2*i], t_max[2*i + 1]);
}
}
void Update(int v)
{
if (lazy[v].fi == -1)
return;
t_min[2*v] = t_max[2*v] = lazy[v];
t_min[2*v + 1] = t_max[2*v + 1] = lazy[v];
lazy[2*v] = lazy[2*v + 1] = lazy[v];
lazy[v] = {-1, 0};
}
void Set(int a, int b, pair<int, int> val, int v = 1, int l = 0, int r = -1)
{
if (r == -1)
r = BASE - 1;
if (b < l || r < a)
return;
if (a <= l && r <= b) {
t_min[v] = t_max[v] = val;
lazy[v] = val;
return;
}
int mid = (l + r)/2;
Update(v);
Set(a, b, val, 2*v, l, mid);
Set(a, b, val, 2*v + 1, mid + 1, r);
t_min[v] = min(t_min[2*v], t_min[2*v + 1]);
t_max[v] = max(t_max[2*v], t_max[2*v + 1]);
}
pair<int, int> Min(int a, int b, int v = 1, int l = 0, int r = -1)
{
if (r == -1)
r = BASE - 1;
if (b < l || r < a)
return {1e9, 0};
if (a <= l && r <= b)
return t_min[v];
int mid = (l + r)/2;
Update(v);
auto res_l = Min(a, b, 2*v, l, mid);
auto res_r = Min(a, b, 2*v + 1, mid + 1, r);
t_min[v] = min(t_min[2*v], t_min[2*v + 1]);
t_max[v] = max(t_max[2*v], t_max[2*v + 1]);
return min(res_l, res_r);
}
pair<int, int> Max(int a, int b, int v = 1, int l = 0, int r = -1)
{
if (r == -1)
r = BASE - 1;
if (b < l || r < a)
return {0, 0};
if (a <= l && r <= b)
return t_max[v];
int mid = (l + r)/2;
Update(v);
auto res_l = Max(a, b, 2*v, l, mid);
auto res_r = Max(a, b, 2*v + 1, mid + 1, r);
t_min[v] = min(t_min[2*v], t_min[2*v + 1]);
t_max[v] = max(t_max[2*v], t_max[2*v + 1]);
return max(res_l, res_r);
}
};
struct segTree2 {
vector<pair<int, int>> t;
int BASE;
int c;
segTree2(int n)
{
c = 0;
BASE = 1;
while (BASE <= n)
BASE *= 2;
t.resize(2*BASE + 7, {0, 0});
}
void Set(int a, int b, int val)
{
++c;
a += BASE - 1;
b += BASE + 1;
while (a/2 != b/2) {
if (a % 2 == 0)
t[a + 1] = {c, val};
if (b % 2 == 1)
t[b - 1] = {c, val};
a /= 2;
b /= 2;
}
}
int Get(int i)
{
i += BASE;
pair<int, int> res = t[i];
while (i /= 2)
res = max(res, t[i]);
return res.se;
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
segTree h(n);
segTree2 lt(n), rt(n);
lt.Set(0, n - 1, 0);
rt.Set(0, n - 1, n - 1);
for (int i = 0; i < k; ++i) {
if (op[i] == 1) {
auto res = h.Min(left[i], right[i]);
while (res.fi < height[i]) {
int l = lt.Get(res.se);
int r = rt.Get(res.se);
if (l < left[i]) {
rt.Set(l, left[i] - 1, left[i] - 1);
l = left[i];
}
if (r > right[i]) {
lt.Set(right[i] + 1, r, right[i] + 1);
h.Set(right[i] + 1, r, {res.fi, right[i] + 1});
r = right[i];
}
h.Set(l, r, {height[i], l});
if (h.Max(l - 1, l - 1).fi == height[i])
l = lt.Get(l - 1);
if (h.Max(r + 1, r + 1).fi == height[i])
r = rt.Get(r + 1);
lt.Set(l, r, l);
rt.Set(l, r, r);
res = h.Min(left[i], right[i]);
}
} else {
auto res = h.Max(left[i], right[i]);
while (res.fi > height[i]) {
int l = lt.Get(res.se);
int r = rt.Get(res.se);
if (l < left[i]) {
rt.Set(l, left[i] - 1, left[i] - 1);
l = left[i];
}
if (r > right[i]) {
lt.Set(right[i] + 1, r, right[i] + 1);
h.Set(right[i] + 1, r, {res.fi, right[i] + 1});
r = right[i];
}
h.Set(l, r, {height[i], l});
if (h.Max(l - 1, l - 1).fi == height[i])
l = lt.Get(l - 1);
if (h.Max(r + 1, r + 1).fi == height[i])
r = rt.Get(r + 1);
lt.Set(l, r, l);
rt.Set(l, r, r);
res = h.Max(left[i], right[i]);
}
}
}
for (int i = 1; i < h.BASE; ++i)
h.Update(i);
for (int i = 0; i < n; ++i)
finalHeight[i] = h.t_max[h.BASE + i].fi;
return;
}
