#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
typedef long long ll;
const int inf=(1<<30);
struct node
{
int a,b;
node(){a=0;b=inf;}
node(int x,int y){a=x;b=y;}
int eval(int x)
{
if(x<=a) return a;
else if(a<=x&&x<=b) return x;
else return b;
}
void pull(node &l,node &r)
{
a=r.eval(l.a);
b=r.eval(l.b);
}
};
const int N=500000;
node tree[4*N];
void update(int idx,int l,int r,int pos,node x)
{
if(l==r) tree[idx]=x;
else
{
int m=(l+r)/2;
if(pos<=m) update(2*idx,l,m,pos,x);
else update(2*idx+1,m+1,r,pos,x);
tree[idx].pull(tree[2*idx],tree[2*idx+1]);
}
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int res[])
{
vector<int> add[n];
vector<int> rm[n];
for(int i=0;i<k;i++)
{
add[left[i]].push_back(i);
rm[right[i]].push_back(i);
}
for(int i=0;i<n;i++)
{
for(int j:add[i])
{
if(op[j]==1) update(1,0,k-1,j,node(height[j],inf));
else update(1,0,k-1,j,node(0,height[j]));
}
res[i]=tree[1].a;
for(int j:rm[i]) update(1,0,k-1,j,node());
}
}
