#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
const int MAXN = 1 << 21;
const int INF = 1e9;
int n, q;
int seg[2 * MAXN];
int kop[2 * MAXN][2];
void kopnij(int v) {
int a = 2 * v;
int b = 2 * v + 1;
seg[a] = min(seg[a], kop[v][0]);
seg[a] = max(seg[a], kop[v][1]);
seg[b] = min(seg[b], kop[v][0]);
seg[b] = max(seg[b], kop[v][1]);
if (kop[a][1] > kop[v][0]) {
kop[a][1] = 0;
}
if (kop[a][0] < kop[v][1]) {
kop[a][0] = INF;
}
if (kop[b][1] > kop[v][0]) {
kop[b][1] = 0;
}
if (kop[b][0] < kop[v][1]) {
kop[b][0] = INF;
}
kop[a][0] = min(kop[a][0], kop[v][0]);
kop[a][1] = max(kop[a][1], kop[v][1]);
kop[b][0] = min(kop[b][0], kop[v][0]);
kop[b][1] = max(kop[b][1], kop[v][1]);
kop[v][0] = INF;
kop[v][1] = 0;
}
void upd(int v, int l, int r, int p, int k, int c, int h) {
if (p <= l && r <= k) {
if (c == 1) {
seg[v] = min(seg[v], h);
kop[v][0] = min(kop[v][0], h);
if (kop[v][1] > h) kop[v][1] = 0;
}
else {
seg[v] = max(seg[v], h);
kop[v][1] = max(kop[v][1], h);
if (kop[v][0] < h) kop[v][0] = INF;
}
}
else if (p > r || k < l) {
}
else {
kopnij(v);
int sr = (l + r)/2;
upd(2 * v, l, sr, p, k, c, h);
upd(2 * v + 1, sr + 1, r, p, k, c, h);
}
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
rep(i, 2 * MAXN) {
kop[i][0] = INF;
}
n = N;
q = k;
rep(i, q) {
op[i] = 3 - op[i];
upd(1, 0, MAXN - 1, left[i], right[i], op[i], height[i]);
}
for (int v = 1; v < MAXN; v++) {
kopnij(v);
}
rep(i, n) {
finalHeight[i] = seg[i + MAXN];
}
return;
}
