#include <bits/stdc++.h>
using namespace std;
const int M = 5e5, inf = 1e6;
int seg[2][M*4],k;
void modify(int ty,int p,int x,int v=1,int s=0,int e=k)
{
if (s+1==e)
{
seg[ty][v]=x;
return;
}
int mid=(s+e)/2,lc=v*2,rc=v*2+1;
if (p<mid)
modify(ty,p,x,lc,s,mid);
else
modify(ty,p,x,rc,mid,e);
if (ty)
seg[ty][v]=min(seg[ty][lc],seg[ty][rc]);
else
seg[ty][v]=max(seg[ty][lc],seg[ty][rc]);
}
int get(int ty,int l,int r,int v=1,int s=0,int e=k)
{
if (r<=s or e<=l)
return ty*inf;
if (l<=s and e<=r)
return seg[ty][v];
int mid=(s+e)/2,lc=v*2,rc=v*2+1;
if (ty)
return min(get(ty,l,r,lc,s,mid),get(ty,l,r,rc,mid,e));
return max(get(ty,l,r,lc,s,mid),get(ty,l,r,rc,mid,e));
}
void buildWall(int n, int K, int op[], int left[], int right[], int height[], int finalHeight[])
{
k=K;
for (int i=0;i<k;i++)
for (int j=0;j<2;j++)
modify(j,i,j*inf);
vector<pair<int,int>> st[2][n],en[2][n];
for (int i=0;i<k;i++)
{
st[op[i]-1][left[i]].push_back({i,height[i]});
en[op[i]-1][right[i]].push_back({i,height[i]});
}
for (int i=0;i<n;i++)
{
for (int j=0;j<2;j++)
for (auto x:st[j][i])
modify(j,x.first,x.second);
int s=-1,e=k;
while (s+1<e)
{
int mid=(s+e)/2;
int x=get(0,mid,k),y=get(1,mid,k);
if (x>y)
s=mid;
else
e=mid;
}
if (s==-1)
finalHeight[i]=get(0,0,k);
else
{
int x=get(0,s,k),y=get(1,s,k);
int x1=get(0,s+1,k),y1=get(1,s+1,k);
if (x==x1)
finalHeight[i]=x;
else
finalHeight[i]=y;
}
for (int j=0;j<2;j++)
for (auto x:en[j][i])
modify(j,x.first,inf*j);
}
}
