#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
const int M = 4.2e6;
bool setMax = 1;
struct Node {
int mini, maxi, lazyMin, lazyMax;
Node() : mini(0), maxi(0), lazyMin(-1), lazyMax(-1) {};
void setMinMax(int _mini, int _maxi) {
mini = _mini;
maxi = _maxi;
}
void mergeLazy(int val, bool type) {
if (val == -1) return;
if (type == setMax) {
lazyMax = min((lazyMax == -1 ? val : lazyMax), val);
maxi = min(maxi, lazyMax);
if (maxi < mini) {
mini = maxi;
lazyMin = lazyMax;
}
} else {
lazyMin = max((lazyMin == -1 ? val : lazyMin), val);
mini = max(mini, lazyMin);
if (maxi < mini) {
maxi = mini;
lazyMax = lazyMin;
}
}
}
} node[M];
void propagate(int head) {
if (node[head].lazyMin == -1 && node[head].lazyMax == -1) return;
int lazyMin = node[head].lazyMin; node[head].lazyMin = -1;
int lazyMax = node[head].lazyMax; node[head].lazyMax = -1;
node[head*2+1].mergeLazy(lazyMin, 0);
node[head*2+1].mergeLazy(lazyMax, 1);
node[head*2+2].mergeLazy(lazyMin, 0);
node[head*2+2].mergeLazy(lazyMax, 1);
}
void update(int l, int r, int L, int R, int val, bool isSetMax, int head) {
if (l > R || L > r) return;
if ((isSetMax && node[head].maxi <= val) ||
(!isSetMax && node[head].mini >= val)) {
return;
}
if (L <= l && r <= R) {
node[head].mergeLazy(val, isSetMax);
return;
}
int mid = (l+r)>>1;
propagate(head);
update(l, mid, L, R, val, isSetMax, head*2+1);
update(mid+1, r, L, R, val, isSetMax, head*2+2);
node[head].setMinMax(
min(node[head*2+1].mini, node[head*2+2].mini),
max(node[head*2+1].maxi, node[head*2+2].maxi)
);
}
void dfs(int l, int r, int res[], int head) {
if (l == r) {
res[l] = node[head].mini;
return;
}
int mid = (l+r)>>1;
propagate(head);
dfs(l, mid, res, head*2+1);
dfs(mid+1, r, res, head*2+2);
}
void buildWall(int n, int k, int t[], int L[], int R[], int H[], int res[]){
int ADD = 1;
n--;
for (int i = 0; i < k; i++) {
// cout << "----------------\n";
if (t[i] == ADD) { // Add, setMin
// cout << "UPDATE: " << L[i] << "," << R[i] << " " << H[i] << " type: 0\n";
update(0, n, L[i], R[i], H[i], 0, 0);
} else { // REMOVE, setMax
// cout << "UPDATE: " << L[i] << "," << R[i] << " " << H[i] << " type: 1\n";
update(0, n, L[i], R[i], H[i], 1, 0);
}
dfs(0, n, res, 0);
// for (int i = 0; i <= n; i++) cout << res[i] << " \n"[i==n];
}
// cout << "=====================\n";
dfs(0, n, res, 0);
return;
}
