/** * * * * * * * * * * * * * * **\
* *
* Author: Haidara Nassour *
* Coded in: 2021\09\12 HH:MM:SS *
* Lang: C++ *
* *
\** * * * * * * * * * * * * * * **/
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define test int tests;cin>>tests;while(tests--)
#define itn int
#define rep(i,x,n) for(int i=(x);i<(n);i++)
#define FOR(i,n) rep(i,0,n)
#define per(i,x,n) for(int i=(x);i>(n);i--)
#define ROF(i,x) for(int i=x;i>=0;i--)
#define v(i) vector< i >
#define p(i,j) pair< i , j >
#define pii pair<int,int>
#define m(i,j) map< i , j >
#define um(i,j) unordered_map< i , j >
#define max_heap(i) priority_queue< i >
#define min_heap(i) priority_queue< i , vector< i > ,greater< i > >
#define ff first
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ss second
#define pp push_back
#define debug(x) cout<<#x<<" ";
using namespace std;
const int inf=1LL<<30LL;
const int mod=998244353;
const int maxn=20200;
int n;
struct node
{
int setdown=inf,setup=0,maxtall=inf,mintall=0,last=0;
/// setdown -> all buildings greater than it will equal to it
/// setup -> all buildings smaller than it will equal to it
} st[maxn*4];
bool add=0;
int val;
void pull(int inx,int l,int r)
{
st[inx].mintall=max(st[inx].mintall,st[inx].setup);
st[inx].maxtall=min(st[inx].maxtall,st[inx].setdown);
if(add)
st[inx].last=0;
else
st[inx].last=1;
if(l!=r)
{
st[inx*2].setup=max(st[inx*2].setup,st[inx].setup);
st[inx*2].setdown=min(st[inx*2].setdown,st[inx].setdown);
st[inx*2+1].setup=max(st[inx*2+1].setup,st[inx].setup);
st[inx*2+1].setdown=min(st[inx*2+1].setdown,st[inx].setdown);
}
st[inx].setdown=inf;
st[inx].setup=0;
}
void update(int ul,int ur,int l=1,int r=n,int inx=1)
{
pull(inx,l,r);
if(ul<=l&&r<=ur)
{
/// setdown -> all buildings greater than it will equal to it
/// setup -> all buildings smaller than it will equal to it
if(add)
st[inx].setup=val;
else
st[inx].setdown=val;
pull(inx,l,r);
return ;
}
if(l>ur||ul>r)
return ;
int mid=l+(r-l)/2;
update(ul,ur,l,mid,inx*2);
update(ul,ur,mid+1,r,inx*2+1);
}
int query(int pos,int l=1,int r=n,int inx=1)
{
pull(inx,l,r);
if(l==r)
{
if(!st[inx].last)
return st[inx].mintall;
return st[inx].maxtall;
}
int mid=l+(r-l)/2;
if(pos<=mid)
return query(pos,l,mid,inx*2);
return query(pos,mid+1,r,inx*2+1);
}
void buildWall(int sz, int k, int op[], int left[], int right[],int height[], int finalHeight[])
{
n=sz;
FOR(i,k)
{
right[i]++;
left[i]++;
add=0;
val=height[i];
if(op[i]==1)
add=1,update(left[i],right[i]);
else
update(left[i],right[i]);
}
FOR(i,n)
finalHeight[i]=query(i+1);
}
