#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
using namespace std;
#include "wall.h"
const int inf=1e9+10,c=5e5+5;
struct node
{
int mx=0,mn=inf;
};
node combine(node a, node b)
{
node x;
x.mx=max(a.mx,b.mx);
x.mn=min(a.mn,b.mn);
return x;
}
node val[4*c];
void upd(int cs, int tl, int tr, int pos, int tip, int x)
{
if(tl==tr)
{
if(tip==1) val[cs].mx=x;
else val[cs].mn=x;
return;
}
int mid=(tl+tr)/2;
if(pos<=mid) upd(2*cs,tl,mid,pos,tip,x);
else upd(2*cs+1,mid+1,tr,pos,tip,x);
val[cs]=combine(val[2*cs],val[2*cs+1]);
}
node query(int cs, int tl, int tr, int l, int r)
{
if(l>r) return {0,inf};
if(l==tl && r==tr) return val[cs];
int mid=(tl+tr)/2;
return combine(query(2*cs,tl,mid,l,min(r,mid)),query(2*cs+1,mid+1,tr,max(mid+1,l),r));
}
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int fh[]){
for(int i=1; i<=4*k; i++)
val[i]={0,inf};
vector<vector<array<int, 3>>> be(n+1),ki(n+1);
for(int i=0; i<k; i++)
{
be[l[i]].push_back({op[i],h[i],i});
ki[r[i]+1].push_back({op[i],i,0});
}
int db=0;
for(int i=0; i<n; i++)
{
for(auto &[o,mag,ind]:be[i])
{
upd(1,0,k-1,ind,o,mag);
db++;
}
for(auto &[o,ind,dsa]:ki[i])
{
if(o==1) upd(1,0,k-1,ind,1,0);
else upd(1,0,k-1,ind,2,inf);
db--;
}
if(db>0)
{
int lo=-1,hi=k-1; //hi: ahol meg nagy<kis
while(lo<hi-1)
{
int mid=(lo+hi)/2;
auto x=query(1,0,k-1,mid,k-1);
if(x.mx<x.mn) hi=mid;
else lo=mid;
}
if(lo<0)
{
fh[i]=val[1].mx;
}
else
{
auto x=query(1,0,k-1,hi,k-1);
auto y=query(1,0,k-1,lo,k-1);
bool maxi=0;
if(x.mn!=y.mn) maxi=1;
if(maxi) fh[i]=x.mx;
else fh[i]=x.mn;
}
}
}
return;
}
