#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> segtree;
void add(int l, int r, int val){
while (l <= r){
if (l%2 == 1) {
segtree[l] = max(val, segtree[l]);
l++;
}
if (r%2 == 0){
segtree[r] = max(val, segtree[r]);
r--;
}
l /= 2;
r /= 2;
}
}
void remove(int l, int r, int val){
while (l <= r){
if (l%2 == 1) {
segtree[l] = min(val, segtree[l]);
l++;
}
if (r%2 == 0){
segtree[r] = min(val, segtree[r]);
r--;
}
l /= 2;
r /= 2;
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
int zp = (int)(1 << (int)ceil(log2(n)));
//cerr << zp << endl;
segtree.resize(2*zp);
int i;
for (i=0; i<k; i++){
if (op[i] == 2) break;
add(left[i]+zp, right[i]+zp, height[i]);
}
for (int j=1; j<zp; j++){
segtree[j*2] = max(segtree[j*2], segtree[j]);
segtree[j*2+1] = max(segtree[j*2+1], segtree[j]);
segtree[j] = 1e9;
}
for (;i<k; i++){
remove(left[i]+zp, right[i]+zp, height[i]);
}
for (int j=1; j<zp; j++){
segtree[j*2] = min(segtree[j*2], segtree[j]);
segtree[j*2+1] = min(segtree[j*2+1], segtree[j]);
segtree[j] = 0;
}
for (int j=0; j<n; j++){
finalHeight[j] = segtree[j+zp];
}
return;
}
