#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
#include <set>
#include <cmath>
#include <climits>
#include <cstring>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
const int N = 1<<21;
int a[2*N + 5], b[2*N + 5];
void updateChild(int curr, int child){
a[child] = min(a[child], a[curr]);
a[child] = max(a[child], b[curr]);
b[child] = max(b[child], b[curr]);
b[child] = min(b[child], a[curr]);
}
void updateSeg(int curr, int l, int r, int beg, int end, int type, int h){
if (l > end || r < beg)
return;
if (l >= beg && r <= end){
if (!type){
a[curr] = max(a[curr], h);
b[curr] = max(b[curr], h);
}
else{
b[curr] = min(b[curr], h);
a[curr] = min(a[curr], h);
}
return;
}
updateChild(curr, 2*curr + 1);
updateChild(curr, 2*curr + 2);
a[curr] = N; b[curr] = 0;
int mid = (l + r)/2;
updateSeg(2*curr + 1, l, mid, beg, end, type, h);
updateSeg(2*curr + 2, mid + 1, r, beg, end, type, h);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
std::ios::sync_with_stdio(false);
for (int i = 0; i < k; i++){
updateSeg(0, 0, N - 1, left[i], right[i], op[i] - 1, height[i]);
}
for (int i = 0; i < N - 1; i++){
updateChild(i, 2*i + 1);
updateChild(i, 2*i + 2);
}
for (int i = N - 1; i < N + n - 1; i++)
finalHeight[i - (N - 1)] = min(a[i], b[i]);
}
