#include<bits/stdc++.h>
#include"wall.h"
using namespace std;
typedef long long ll;
struct segtree{
struct node{
int min_opt, max_opt;
node() : min_opt(1e9), max_opt(0){}
};
vector<node> tree;
int N;
segtree(const int& treesize) : N(treesize){
tree.resize(4*N+5);
}
void push(int v, bool side){
int where = (side ? v*2+1 : v*2);
if(tree[v].min_opt != 1e9){
tree[where].min_opt = min(tree[where].min_opt, tree[v].min_opt);
tree[where].max_opt = min(tree[where].max_opt, tree[where].min_opt);
if(side)
tree[v].min_opt = 1e9;
}
if(tree[v].max_opt != 0){
tree[where].max_opt = max(tree[where].max_opt, tree[v].max_opt);
tree[where].min_opt = max(tree[where].min_opt, tree[where].max_opt);
if(side)
tree[v].max_opt = 0;
}
}
void max_update(int v, int l, int r, int L, int R, int D){
if(l > R || r < L){
return;
}
if(r <= R && l >= L){
tree[v].max_opt = max(tree[v].max_opt, D);
tree[v].min_opt = max(tree[v].min_opt, tree[v].max_opt);
return;
}
push(v, 0);
push(v, 1);
int mid = (l+r)/2;
max_update(v*2, l, mid, L, R, D);
max_update(v*2+1, mid+1, r, L, R, D);
}
void min_update(int v, int l, int r, int L, int R, int D){
if(l > R || r < L){
return;
}
if(r <= R && l >= L){
tree[v].min_opt = min(tree[v].min_opt, D);
tree[v].max_opt = min(tree[v].max_opt, tree[v].min_opt);
return;
}
push(v, 0);
push(v, 1);
int mid = (l+r)/2;
min_update(v*2, l, mid, L, R, D);
min_update(v*2+1, mid+1, r, L, R, D);
}
void max_update(int L, int R, int D){
max_update(1, 0, N, L, R, D);
}
void min_update(int L, int R, int D){
min_update(1, 0, N, L, R, D);
}
int get(int v, int l, int r, int I){
if(l == r)
return max(min(0, tree[v].min_opt), tree[v].max_opt);
push(v, 0);
push(v, 1);
int mid = (l+r)/2;
if(I <= mid)
return get(v*2, l, mid, I);
else
return get(v*2+1, mid+1, r, I);
}
int operator[](int I){
return get(1, 0, N, I);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
segtree ST(n);
for(int i = 0; i < k; i++){
if(op[i] == 1){
ST.max_update(left[i], right[i], height[i]);
} else{
ST.min_update(left[i], right[i], height[i]);
}
}
for(int i = 0; i < n; i++)
finalHeight[i] = ST[i];
}
