#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
int n;
vector<pair<int,int>> st;
pair<int,int> merge(pair<int,int> a, pair<int,int> b){
if (b.first > a.second) return {b.first, b.first};
if (b.second < a.first) return {b.second, b.second};
return {max(a.first, b.first), min(a.second, b.second)};
}
void pushdown(int node, int tl, int tr){
if (tl == tr) return;
st[node*2] = merge(st[node*2], st[node]);
st[node*2+1] = merge(st[node*2+1], st[node]);
st[node] = {0, 100000};
}
void update(int l, int r, int lo, int hi, int node=1, int tl=0, int tr=n-1){
pushdown(node, tl, tr);
if (l <= tl && tr <= r){
st[node] = merge(st[node], {lo, hi});
return;
}
int tm = (tl+tr)/2;
if (l <= tm) update(l, r, lo, hi, node*2, tl, tm);
if (tm+1 <= r) update(l, r, lo, hi, node*2+1, tm+1, tr);
}
int query(int pos, int node=1, int tl=0, int tr=n-1){
pushdown(node, tl, tr);
if (tl == tr) return st[node].first;
int tm = (tl+tr)/2;
if (pos <= tm) return query(pos, node*2, tl, tm);
else return query(pos, node*2+1, tm+1, tr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
::n = n;
st.resize(4*n, {0, 100000});
for (int i=0; i<k; i++){
if (op[i] == 1) update(left[i], right[i], height[i], 100000);
if (op[i] == 2) update(left[i], right[i], 0, height[i]);
}
for (int i=0; i<n; i++) finalHeight[i] = query(i);
return;
}
