#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int MAXN = 2e6 + 10;
int mx[4*MAXN], mn[4*MAXN];
void add(int pos, int maxi, int mini) {
if (mx[pos] > mini)
mx[pos] = mn[pos] = mini;
else if (mn[pos] < maxi)
mx[pos] = mn[pos] = maxi;
else {
mx[pos] = max(mx[pos], maxi);
mn[pos] = min(mn[pos], mini);
}
}
void refresh(int pos, int ini, int fim) {
if (ini != fim) {
add(2*pos, mx[pos], mn[pos]);
add(2*pos + 1, mx[pos], mn[pos]);
mx[pos] = 0;
mn[pos] = 1e9;
}
}
void update(int pos, int ini, int fim, int l, int r, int maxi, int mini) {
refresh(pos, ini, fim);
if (l <= ini && fim <= r) {
add(pos, maxi, mini);
refresh(pos, ini, fim);
return;
}
if (r < ini || fim < l) return;
int m = (ini + fim)/2;
update(2*pos, ini, m, l, r, maxi, mini);
update(2*pos + 1, m + 1, fim, l, r, maxi, mini);
}
void build(int pos, int ini, int fim, int ans[]) {
if (ini == fim) {
ans[ini] = mx[pos];
return;
}
refresh(pos, ini, fim);
int m = (ini + fim)/2;
build(2*pos, ini, m, ans);
build(2*pos + 1, m + 1, fim, ans);
}
void buildWall(int n, int q, int ops[], int ls[], int rs[], int hs[], int ans[]) {
for (int i = 1; i <= 4*n; ++i)
mn[i] = 1e9;
for (int i = 0; i < q; ++i)
if (ops[i] == 1) update(1, 0, n-1, ls[i], rs[i], hs[i], 1e9);
else update(1, 0, n-1, ls[i], rs[i], 0, hs[i]);
build(1, 0, n-1, ans);
}
