#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair<int, int>
#define ll long long
const int BIG = 2e9 + 500;
struct segTree
{
struct Node
{
deque<pii> ops;
};
vector<Node> tree;
int sz;
void init(int n)
{
sz = 1;
while (sz < n)
sz *= 2;
tree.resize(2 * sz);
}
// 0 - min=
// 1 - max=
int C1, C2, C3;
void upd(int v, pii &op)
{
// cout << lv << " " << rv << " " << op.f << " " << op.s << "!!!\n";
if (tree[v].ops.size() and op.f == tree[v].ops.back().f)
tree[v].ops.back().s = (op.f == 0 ? min(op.s, tree[v].ops.back().s) : max(op.s, tree[v].ops.back().s));
else if (tree[v].ops.size() < 2)
tree[v].ops.push_back(op);
else
{
if (op.f == 1)
{
C1 = tree[v].ops.begin()->s;
tree[v].ops.pop_front();
C2 = tree[v].ops.begin()->s;
C3 = op.s;
tree[v].ops.push_back({1, max(min(C1, C2), C3)});
}
else
{
C1 = tree[v].ops.begin()->s;
tree[v].ops.pop_front();
C2 = tree[v].ops.begin()->s;
C3 = op.s;
tree[v].ops.push_back({0, min(max(C1, C2), C3)});
}
}
assert(tree[v].ops.size() <= 2);
}
void push(int v, int lv, int rv)
{
if (rv - lv == 1)
return;
while (tree[v].ops.size())
{
pii op = tree[v].ops.front();
tree[v].ops.pop_front();
upd(v * 2 + 1, op);
upd(v * 2 + 2, op);
}
assert(tree[v].ops.size() == 0);
}
void addOp(int l, int r, pii &op, int v, int lv, int rv)
{
push(v, lv, rv);
if (l <= lv and rv <= r)
{
upd(v, op);
return;
}
if (rv <= l or r <= lv)
return;
int m = (lv + rv) >> 1;
addOp(l, r, op, v * 2 + 1, lv, m);
addOp(l, r, op, v * 2 + 2, m, rv);
}
void addOp(int l, int r, pii op)
{
addOp(l, r, op, 0, 0, sz);
}
void outArray(vector<int> &a, int v, int lv, int rv)
{
push(v, lv, rv);
if (rv - lv == 1)
{
if (lv < a.size())
{
while (tree[v].ops.size())
{
pii op = tree[v].ops.front();
tree[v].ops.pop_front();
a[lv] = op.f ? max(a[lv], op.s) : min(a[lv], op.s);
}
}
return;
}
int m = (lv + rv) >> 1;
outArray(a, v * 2 + 1, lv, m);
outArray(a, v * 2 + 2, m, rv);
}
void outArray(vector<int> &a)
{
outArray(a, 0, 0, sz);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
vector<int> a;
for (int i = 0; i < n; ++i)
a.push_back(finalHeight[i]);
segTree tree;
tree.init(n);
for (int i = 0; i < k; ++i)
{
op[i]--;
tree.addOp(left[i], right[i] + 1, {1 - op[i], height[i]});
}
tree.outArray(a);
for (int i = 0; i < n; ++i)
finalHeight[i] = a[i];
return;
}
// int main()
// {
// int n;
// int k;
// int i, j;
// int status = 0;
// status = scanf("%d%d", &n, &k);
// assert(status == 2);
// int *op = (int *)calloc(sizeof(int), k);
// int *left = (int *)calloc(sizeof(int), k);
// int *right = (int *)calloc(sizeof(int), k);
// int *height = (int *)calloc(sizeof(int), k);
// int *finalHeight = (int *)calloc(sizeof(int), n);
// for (i = 0; i < k; i++)
// {
// status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
// assert(status == 4);
// }
// buildWall(n, k, op, left, right, height, finalHeight);
// for (j = 0; j < n; j++)
// printf("%d\n", finalHeight[j]);
// return 0;
// }
