#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int
MAX = 1e6 + 5,
INF = 1e6;
int lazy[4 * MAX][5];
int a[MAX];
int reduce(const int &a, const int &b, bool &ok) {
int x = abs(a);
int y = abs(b);
if(a < 0 && b < 0)
return (x <= y) ? a : b;
if(a >= 0 && b >= 0)
return (x <= y) ? b : a;
ok = false;
return 0;
}
void transform(int &a, int &b) {
int x = abs(a);
int y = abs(b);
if(a < 0 && b >= 0) {
if(x <= y) {
a = INF;
b *= -1;
}
else swap(a, b);
}
else {
assert(b < 0);
if(x <= y)
swap(a, b);
else {
a = -1;
b *= -1;
}
}
}
void reduce(int a, int b) {
for(int i = 1; i <= lazy[b][0]; i++) {
int p = ++lazy[a][0];
lazy[a][p] = lazy[b][i];
}
assert(lazy[a][0] <= 4);
int s[lazy[a][0]]; int k = 0;
for(int i = 1; i <= lazy[a][0]; i++) {
int o = lazy[a][i];
if(k == 0) {
s[k++] = o;
continue;
}
int x = s[k - 1];
k--;
bool ok = true;
int r = reduce(x, o, ok);
if(ok)
s[k++] = r;
else {
if(k == 0) {
s[k++] = x;
s[k++] = o;
}
else {
int y = s[k - 1];
k--;
transform(y, x);
s[k++] = y;
ok = true;
r = reduce(x, o, ok);
assert(ok);
s[k++] = r;
}
}
}
lazy[a][0] = k;
for(int i = 0; i < k; i++)
lazy[a][i + 1] = s[i];
}
void build(int x, int st, int nd) {
lazy[x][++lazy[x][0]] = 0;
if(st == nd) return;
int mid = (st + nd) >> 1;
build(2 * x, st, mid);
build(2 * x + 1, mid + 1, nd);
}
void prop(int x, int st, int nd) {
if(lazy[x][0] == 1 && lazy[x][1] == 0)
return;
if(st == nd) {
for(int i = 1; i <= lazy[x][0]; i++) {
int o = lazy[x][i];
if(o >= 0)
a[st] = max(a[st], o);
else a[st] = min(a[st], -o);
}
}
else {
reduce(2 * x, x);
reduce(2 * x + 1, x);
}
lazy[x][0] = 0;
lazy[x][++lazy[x][0]] = 0;
}
void upd(int x, int st, int nd, int a, int b, const int &o) {
prop(x, st, nd);
if(st > b || nd < a)
return;
if(st >= a && nd <= b) {
lazy[x][0] = 0;
lazy[x][++lazy[x][0]] = o;
prop(x, st, nd);
return;
}
int mid = (st + nd) >> 1;
upd(2 * x, st, mid, a, b, o);
upd(2 * x + 1, mid + 1, nd, a, b, o);
}
void buildWall(int n, int m, int operation[], int l[], int r[], int h[], int ans[]) {
build(1, 0, n - 1);
for(int i = 0; i < m; i++) {
int height = h[i] + 1;
if(operation[i] == 1)
upd(1, 0, n - 1, l[i], r[i], height);
else upd(1, 0, n - 1, l[i], r[i], -height);
}
for(int i = 0; i < n; i++) {
upd(1, 0, n - 1, i, i, 0);
ans[i] = max(0, a[i] - 1);
}
}
