#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int
MAX = 2e6 + 5,
INF = 1e6;
pair <int, int> lazy[4 * MAX];
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) {
int arr[4] = { lazy[a].first, lazy[a].second, lazy[b].first, lazy[b].second };
int s[4] = { 0, 0, 0, 0 };
int k = 0;
for(int i = 0; i < 4; i++) {
int o = arr[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] = { s[0], s[1] };
}
inline int apply(int x, int y) { return (y >= 0) ? max(x, y) : min(x, -y); }
void build(int x, int st, int nd) {
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] == make_pair(0, 0))
return;
if(st == nd) {
a[st] = apply(a[st], lazy[x].first);
a[st] = apply(a[st], lazy[x].second);
}
else {
reduce(2 * x, x);
reduce(2 * x + 1, 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] = { o, 0 };
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);
}
}
