#include "wall.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
typedef long long llong;
const int MAXN = 2000000 + 10;
const int INF = 1e9;
int n, q;
struct SegmentTree
{
struct Node
{
int min;
int max;
int lazy;
Node()
{
min = max = 0;
lazy = -1;
}
};
Node tree[4*MAXN];
Node combine(Node left, Node right)
{
Node res;
res.min = std::min(left.min, right.min);
res.max = std::max(left.max, right.max);
return res;
}
void push(int node, int l, int r)
{
if (tree[node].lazy == -1)
{
return;
}
tree[node].min = tree[node].lazy;
tree[node].max = tree[node].lazy;
if (l < r)
{
tree[2*node].lazy = tree[node].lazy;
tree[2*node + 1].lazy = tree[node].lazy;
}
tree[node].lazy = -1;
}
void updateMAX(int l, int r, int node, int queryL, int queryR, int val)
{
push(node, l, r);
if (r < queryL || queryR < l || tree[node].min >= val)
{
return;
}
if (queryL <= l && r <= queryR && tree[node].max <= val)
{
tree[node].lazy = val;
push(node, l, r);
return;
}
int mid = (l + r) / 2;
updateMAX(l, mid, 2*node, queryL, queryR, val);
updateMAX(mid + 1, r, 2*node + 1, queryL, queryR, val);
tree[node] = combine(tree[2*node], tree[2*node + 1]);
}
void updateMIN(int l, int r, int node, int queryL, int queryR, int val)
{
push(node, l, r);
if (r < queryL || queryR < l || tree[node].max <= val)
{
return;
}
if (queryL <= l && r <= queryR && tree[node].min >= val)
{
tree[node].lazy = val;
push(node, l, r);
return;
}
int mid = (l + r) / 2;
updateMIN(l, mid, 2*node, queryL, queryR, val);
updateMIN(mid + 1, r, 2*node + 1, queryL, queryR, val);
tree[node] = combine(tree[2*node], tree[2*node + 1]);
}
void assignANS(int l, int r, int node, int to[])
{
push(node, l, r);
if (l == r)
{
to[l - 1] = tree[node].min;
return;
}
int mid = (l + r) / 2;
assignANS(l, mid, 2*node, to);
assignANS(mid + 1, r, 2*node + 1, to);
}
void updateMIN(int l, int r, int val)
{
updateMIN(1, n, 1, l, r, val);
}
void updateMAX(int l, int r, int val)
{
updateMAX(1, n, 1, l, r, val);
}
void assignANS(int to[])
{
assignANS(1, n, 1, to);
}
};
SegmentTree tree;
void buildWall(int N, int Q, int op[], int left[], int right[], int height[], int finalHeight[])
{
n = N;
q = Q;
for (int i = 0 ; i < q ; ++i)
{
if (op[i] == 1)
{
tree.updateMAX(left[i] + 1, right[i] + 1, height[i]);
} else
{
tree.updateMIN(left[i] + 1, right[i] + 1, height[i]);
}
}
tree.assignANS(finalHeight);
return;
}
