#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
const int M = 4*N;
const int MIN = 0, MAX = 1e5;
struct Node {
int minVal, maxVal, lazyMin, lazyMax;
bool isAdd;
Node() {
isAdd = 0;
lazyMin = MIN;
lazyMax = MAX;
minVal = maxVal = 0;
}
Node(int a, int b, int c, int d, bool e) {
minVal = a;
maxVal = b;
lazyMin = c;
lazyMax = d;
isAdd = e;
}
};
Node node[M];
void propagate(int head) {
if (node[head].lazyMin == MIN && node[head].lazyMax == MAX) return;
int x = node[head].lazyMin; node[head].lazyMin = MIN;
int y = node[head].lazyMax; node[head].lazyMax = MAX;
for (int add = 1; add <= 2; add++) {
node[head*2+add].minVal = max(node[head*2+add].minVal, x);
node[head*2+add].lazyMin = max(node[head*2+add].lazyMin, x);
if (x > node[head*2+add].maxVal) {
node[head*2+add].maxVal = x;
node[head*2+add].lazyMax = x;
}
}
for (int add = 1; add <= 2; add++) {
node[head*2+add].maxVal = min(node[head*2+add].maxVal, y);
node[head*2+add].lazyMax = min(node[head*2+add].lazyMax, y);
if (y < node[head*2+add].minVal) {
node[head*2+add].minVal = y;
node[head*2+add].lazyMin = y;
}
}
}
void update(int l, int r, int L, int R, int val, bool isAdd, int head) {
if (l > R || L > r) return;
if (isAdd && node[head].minVal >= val) return;
if (!isAdd && node[head].maxVal <= val) return;
if (L <= l && r <= R) {
// cout << "UPDATE: " << l << ' ' << r << '\n';
if (isAdd) {
node[head].minVal = max(node[head].minVal, val);
node[head].lazyMin = max(node[head].lazyMin, val);
if (val > node[head].maxVal) {
node[head].maxVal = val;
node[head].lazyMax = val;
}
} else {
node[head].maxVal = min(node[head].maxVal, val);
node[head].lazyMax = min(node[head].lazyMax, val);
if (val < node[head].minVal) {
node[head].minVal = val;
node[head].lazyMin = val;
}
}
return;
}
int mid = (l+r)>>1;
propagate(head);
update(l, mid, L, R, val, isAdd, head*2+1);
update(mid+1, r, L, R, val, isAdd, head*2+2);
node[head] = Node({
min(node[head*2+1].minVal, node[head*2+2].minVal),
max(node[head*2+1].maxVal, node[head*2+2].maxVal),
MIN,
MAX,
0
});
}
void dfs(int l, int r, int res[], int head) {
// cout << l << "," << r << ": " << node[head].minVal << ',' << node[head].maxVal << '\n';
if (l == r) {
// cout << node[head].minVal << " ";
res[l] = node[head].minVal;
return;
}
propagate(head);
int mid = (l+r)>>1;
dfs(l, mid, res, head*2+1);
dfs(mid+1, r, res, head*2+2);
// if (head == 0) cout << "\n";
}
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int res[]) {
for (int i = 0; i < k; i++) {
dfs(0, n-1, res, 0);
update(0, n-1, l[i], r[i], h[i], op[i]==1, 0);
}
dfs(0, n-1, res, 0);
return;
}
