#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define N 2097152
#define inf 100005
struct Query{
int l, r;
};
Query lazy[N << 1];
int tree[N << 1];
void push(int id){
if(id >= N){
tree[id] = min(tree[id], lazy[id].r);
tree[id] = max(tree[id], lazy[id].l);
} else {
if(lazy[id << 1].r <= lazy[id].l){
lazy[id << 1].l = lazy[id].l;
lazy[id << 1].r = lazy[id].l;
} else if(lazy[id << 1].l >= lazy[id].r){
lazy[id << 1].l = lazy[id].r;
lazy[id << 1].r = lazy[id].r;
} else {
lazy[id << 1].l = max(lazy[id << 1].l, lazy[id].l);
lazy[id << 1].r = min(lazy[id << 1].r, lazy[id].r);
}
if(lazy[id << 1 | 1].r <= lazy[id].l){
lazy[id << 1 | 1].l = lazy[id].l;
lazy[id << 1 | 1].r = lazy[id].l;
} else if(lazy[id << 1 | 1].l >= lazy[id].r){
lazy[id << 1 | 1].l = lazy[id].r;
lazy[id << 1 | 1].r = lazy[id].r;
} else {
lazy[id << 1 | 1].l = max(lazy[id << 1 | 1].l, lazy[id].l);
lazy[id << 1 | 1].r = min(lazy[id << 1 | 1].r, lazy[id].r);
}
}
lazy[id].l = 0;
lazy[id].r = inf;
}
void update(int id, int l, int r, int L, int R, int vall, int valr){
if(R < l || L > r) return;
push(id);
if(L <= l && r <= R){
lazy[id].l = vall;
lazy[id].r = valr;
} else {
int m = (l + r) >> 1;
update(id << 1, l, m, L, R, vall, valr);
update(id << 1 | 1, m + 1, r, L, R, vall ,valr);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i = 0; i < k; i++){
if(op[i] == 1)
update(1, 1, N, left[i] + 1, right[i] + 1, height[i], inf);
else
update(1, 1, N, left[i] + 1, right[i] + 1, 0, height[i]);
}
for(int i = 1; i < N * 2; i++)
push(i);
for(int i = 0; i < n; i++){
finalHeight[i] = tree[i + N];
}
}
