#include <bits/stdc++.h>
#include "wall.h"
#include "wall.h"
using namespace std;
class seg_tree{
public:
struct node{
int maxi;
int mini;
};
vector<node> tree;
int N;
node em = {0, INT_MAX};
seg_tree(int K){
N = 1;
while(N <= K){
N *= 2;
}
tree.assign(N * 2, em);
}
node apply(node a, node b){
node c = a;
c.maxi = min(max(a.maxi, b.maxi), b.mini);
c.mini = min(max(a.mini, b.maxi), b.mini);
return c;
}
void propogate(int head, int L, int R){
if(R - L == 1)return;
tree[head * 2 + 1] = apply(tree[head * 2 + 1], tree[head]);
tree[head * 2 + 2] = apply(tree[head * 2 + 2], tree[head]);
tree[head] = em;
}
void mod(int head, int l, int r, int L, int R, int v1, int v2){
propogate(head, L, R);
if(l <= L && R <= r){
if(v2){
tree[head].maxi = max(tree[head].maxi, v1);
tree[head].mini = max(tree[head].mini, v1);
}
else{
tree[head].mini = min(tree[head].mini, v1);
tree[head].maxi = min(tree[head].maxi, v1);
}
return;
}
if(R <= l || L >= r){
return;
}
int mid = (L + R) / 2;
mod(head * 2 + 1, l, r, L, mid, v1, v2);
mod(head * 2 + 2, l, r, mid, R, v1, v2);
}
void mod(int v1, int v2, int l, int r){
mod(0, l, r, 0, N, v1, v2);
}
int get(int head, int L, int R, int pos){
propogate(head, L, R);
if(R-L == 1){
return min(tree[head].maxi, tree[head].mini);
}
int mid = (L + R) / 2;
int ans;
if(pos < mid){
ans = get(head * 2 + 1, L, mid, pos);
}
else{
ans = get(head * 2 + 2, mid, R, pos);
}
return ans;
}
int get(int pos){
return get(0, 0, N, pos);
}
};
void buildWall(int N, int K, int op[], int l[], int r[], int h[], int fh[]){
seg_tree tree(N);
for(int i = 0; i < K; i ++){
int OP = op[i], L = l[i], R = r[i], H = h[i];
if(OP == 1){
tree.mod(H, 1, L, R + 1);
}
else{
tree.mod(H, 0, L, R + 1);
}
}
for(int i = 0; i < N; i ++){
fh[i] = tree.get(i);
}
}
