// mrrrow mnyaa ;3c
// go play vivid/stasis! it's a really awesome free game on steam
enum Type {
UnMarked,
Max,
Min,
Set,
Clamp,
};
const int N = 1 << 4;
int st[N * 2][3];
void merge(int i, Type o, int a, int b = 0) {
switch (st[i][0]) {
case Type::UnMarked:
st[i][0] = o;
st[i][1] = a;
st[i][2] = b;
break;
case Type::Max:
switch (o) {
case Type::Max:
if (a > st[i][1]) st[i][1] = a;
break;
case Type::Min:
if (a <= st[i][1]) st[i][0] = Type::Set, st[i][1] = a;
else st[i][0] = Type::Clamp, st[i][2] = a;
break;
case Type::Set:
st[i][0] = Type::Set;
st[i][1] = a;
break;
case Type::Clamp:
if (st[i][1] > b) st[i][0] = Type::Set, st[i][1] = b;
else st[i][0] = Type::Clamp, st[i][1] = st[i][1] > a ? st[i][1] : a, st[i][2] = b;
break;
}
break;
case Type::Min:
switch (o) {
case Type::Max:
if (a >= st[i][2]) st[i][0] = Type::Set, st[i][1] = a;
else st[i][0] = Type::Clamp, st[i][2] = st[i][1], st[i][1] = a;
break;
case Type::Min:
if (a < st[i][1]) st[i][1] = a;
break;
case Type::Set:
st[i][0] = Type::Set;
st[i][1] = a;
break;
case Type::Clamp:
if (st[i][1] < a) st[i][0] = Type::Set, st[i][1] = a;
else st[i][0] = Type::Clamp, st[i][1] = a, st[i][2] = st[i][2] < b ? st[i][2] : b;
break;
}
break;
case Type::Set:
switch (o) {
case Type::Max:
st[i][1] = st[i][1] > a ? st[i][1] : a;
break;
case Type::Min:
st[i][1] = st[i][1] < a ? st[i][1] : a;
break;
case Type::Set:
st[i][1] = a;
break;
case Type::Clamp:
st[i][1] = st[i][1] <= a ? a : st[i][1] >= b ? b : st[i][1];
break;
}
break;
case Type::Clamp:
switch (o) {
case Type::Max:
if (st[i][2] <= a) st[i][0] = Type::Set, st[i][1] = a;
else st[i][1] = st[i][1] > a ? st[i][1] : a;
break;
case Type::Min:
if (st[i][1] >= a) st[i][0] = Type::Set, st[i][1] = a;
else st[i][2] = st[i][2] < a ? st[i][2] : a;
break;
case Type::Set:
st[i][0] = Type::Set;
st[i][1] = a;
break;
case Type::Clamp:
if (st[i][1] >= b) st[i][0] = Type::Set, st[i][1] = b;
else if (st[i][2] <= a) st[i][0] = Type::Set, st[i][1] = a;
else st[i][1] = st[i][1] > a ? st[i][1] : a, st[i][2] = st[i][2] < b ? st[i][2] : b;
break;
}
break;
}
}
void push(int i) {
if (st[i][0] == Type::UnMarked) return;
merge(i * 2, (Type)st[i][0], st[i][1], st[i][2]);
merge(i * 2 + 1, (Type)st[i][0], st[i][1], st[i][2]);
st[i][0] = Type::UnMarked;
}
void update(Type o, int v, int l, int r, int i = 1, int cl = 0, int cr = N - 1) {
if (l <= cl && cr <= r) {
merge(i, o, v);
return;
}
push(i);
int me = (cl + cr) / 2;
int ms = me + 1;
if (l <= me && cl <= r) update(o, v, l, r, i * 2, cl, me);
if (l <= cr && ms <= r) update(o, v, l, r, i * 2 + 1, ms, cr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
for (int it = 0; it < k; it++) update((Type)op[it], height[it], left[it], right[it]);
for (int i = 0; i < n; i++) {
for (int j = N + i; j; j /= 2) {
switch (st[j][0]) {
case Type::Max:
finalHeight[i] = finalHeight[i] > st[j][1] ? finalHeight[i] : st[j][1];
break;
case Type::Min:
finalHeight[i] = finalHeight[i] < st[j][1] ? finalHeight[i] : st[j][1];
break;
case Type::Set:
finalHeight[i] = st[j][1];
break;
case Type::Clamp:
finalHeight[i] = finalHeight[i] <= st[j][1] ? st[j][1] : finalHeight[i] >= st[j][2] ? st[j][2] : finalHeight[i];
break;
}
}
}
}
