#include "wall.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
using namespace std;
int querySegTree(int n, vector<int> &tree, int p){
int result = 0;
for (p += n; p > 0; p /= 2){
result = max(tree[p], result);
}
return result;
}
void updateSegTree(int n , vector<int> &tree, int l, int r, int t){
l += n;
r += n;
for (; l < r; l /= 2, r /= 2){
if (l % 2 == 1){
tree[l] = max(tree[l], t);
l++;
}
if (r % 2 == 1){
tree[r - 1] = max(tree[r - 1], t);
r--;
}
}
}
int querySegTree2(int n, vector<int> &tree, int p){
int result = 100000;
for (p += n; p > 0; p /= 2){
result = min(tree[p], result);
}
return result;
}
void updateSegTree2(int n , vector<int> &tree, int l, int r, int t){
l += n;
r += n;
for (; l < r; l /= 2, r /= 2){
if (l % 2 == 1){
tree[l] = min(tree[l], t);
l++;
}
if (r % 2 == 1){
tree[r - 1] = min(tree[r - 1], t);
r--;
}
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
vector<int> max_tree (2 * n, 0);
vector<int> min_tree (2 * n, 100000);
//
// updateSegTree(n, max_tree, 2, 7, 10);
// updateSegTree(n, max_tree, 3, 5, 12);
//
// for (int i = 0; i < n; i++){
// cout << querySegTree(n, max_tree, i) << ' ';
// }
// cout << endl;
for (int i = 0; i < k; i++){
if (op[i] == 1){
updateSegTree(n, max_tree, left[i], right[i] + 1, height[i]);
} else {
updateSegTree2(n, min_tree, left[i], right[i] + 1, height[i]);
}
}
for (int i = 0; i < n; i++){
finalHeight[i] = min(querySegTree(n, max_tree, i), querySegTree2(n, min_tree, i));
//cout << i << ' ' << querySegTree(n, max_tree, i) << ' ' << querySegTree2(n, min_tree, i) << endl;
}
return;
}
