#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int segmin[4*2000005], segmax[4*2000005], lazy[4*2000005];
void lazypropagate(int n, int l, int r) {
if (lazy[n] != -1) {
segmin[n] = lazy[n];
segmax[n] = lazy[n];
if (l != r) {
lazy[2*n] = lazy[n];
lazy[2*n+1] = lazy[n];
}
lazy[n] = -1;
}
}
void update1(int n, int l, int r, int a, int b, int h) {
lazypropagate(n, l, r);
if (b < l || r < a || segmin[n] >= h) {
return;
}
if (a <= l && r <= b && segmax[n] < h) {
lazy[n] = h;
lazypropagate(n, l, r);
} else {
int m = (l+r)/2;
update1(2*n, l, m, a, b, h);
update1(2*n+1, m+1, r, a, b, h);
segmax[n] = max(segmax[2*n], segmax[2*n+1]);
segmin[n] = min(segmin[2*n], segmin[2*n+1]);
}
}
void update2(int n, int l, int r, int a, int b, int h) {
lazypropagate(n, l, r);
if (b < l || r < a || segmax[n] <= h) {
return;
}
if (a <= l && r <= b && segmin[n] > h) {
lazy[n] = h;
lazypropagate(n, l, r);
} else {
int m = (l+r)/2;
update2(2*n, l, m, a, b, h);
update2(2*n+1, m+1, r, a, b, h);
segmax[n] = max(segmax[2*n], segmax[2*n+1]);
segmin[n] = min(segmin[2*n], segmin[2*n+1]);
}
}
int query(int n, int l, int r, int i) {
lazypropagate(n, l, r);
if (l == r) {
return segmax[n];
} else {
int m = (l+r)/2;
if (l <= i && i <= m) {
return query(2*n, l, m, i);
} else {
return query(2*n+1, m+1, r, i);
}
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
for (int i = 0; i < k; i++) {
if (op[i] == 1) {
update1(1, 0, n-1, left[i], right[i], height[i]);
} else {
update2(1, 0, n-1, left[i], right[i], height[i]);
}
}
for (int i = 0; i < n; i++) {
finalHeight[i] = query(1, 0, n-1, i);
}
return;
}
