#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;
}
}
}
pair <int, int> reduce(pair <int, int> a, pair <int, int> b) {
transform(a.second, b.first);
bool ok = true;
int r1 = reduce(a.first, a.second, ok);
ok = true;
int r2 = reduce(b.first, b.second, ok);
ok = true;
int r = reduce(r1, r2, ok);
if(ok) {
if(r < 0)
return { r, 0 };
return { -INF, r };
}
if(r1 >= 0)
transform(r1, r2);
return { r1, r2 };
}
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] = { -INF, 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(-INF, 0))
return;
if(st == nd) {
a[st] = apply(a[st], lazy[x].first);
a[st] = apply(a[st], lazy[x].second);
}
else {
lazy[2 * x] = reduce(lazy[2 * x], lazy[x]);
lazy[2 * x + 1] = reduce(lazy[2 * x + 1], lazy[x]);
}
lazy[x] = { -INF, 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) {
if(o < 0)
lazy[x] = { o, 0 };
else lazy[x] = { -INF, 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, 1);
ans[i] = max(0, a[i] - 1);
}
}
