#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=2e6+5;
struct segtree
{
struct node
{
int low, up;
node(): low(0), up(INT_MAX){}
} d[4*nx];
void add(int l, int r, int i, int ql, int qr, int t)
{
if (qr<l||r<ql) return;
t=max(t, d[i].low);
t=min(t, d[i].up);
if (ql<=l&&r<=qr) return void(d[i].low=t);
int md=(l+r)/2;
add(l, md, 2*i, ql, qr, t);
add(md+1, r, 2*i+1, ql, qr, t);
}
void remove(int l, int r, int i, int ql, int qr, int t)
{
if (qr<l||r<ql) return;
t=max(t, d[i].low);
t=min(t, d[i].up);
if (ql<=l&&r<=qr) return void(d[i].up=t);
int md=(l+r)/2;
remove(l, md, 2*i, ql, qr, t);
remove(md+1, r, 2*i+1, ql, qr, t);
}
int query(int l, int r, int i, int idx, int t)
{
t=max(t, d[i].low);
t=min(t, d[i].up);
if (l==r) return t;
int md=(l+r)/2;
if (idx<=md) return query(l, md, 2*i, idx, t);
else return query(md+1, r, 2*i+1, idx, t);
}
} s;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i=k-1; i>=0; i--)
{
if (op[i]==1) s.add(0, n-1, 1, left[i], right[i], height[i]);
else s.remove(0, n-1, 1, left[i], right[i], height[i]);
}
for (int i=0; i<n; i++) finalHeight[i]=s.query(0, n-1, 1, i, 0);
}
