#include<algorithm>
#include<vector>
using namespace std;
struct Node{ int Max,Min; };
Node tree[1<<22]; // 구간의 최대, 최소
struct Lazy{ int type,value; };
vector<Lazy> lazy[1<<22]; // type이 0이면 하한, 1이면 상한 설정.
int base=1<<21;
void check(int type,int value,int now)
{
if(lazy[now].size()==0) lazy[now].push_back({type,value});
else if(lazy[now].size()==1)
{
if(lazy[now][0].type==type)
{
if(lazy[now][0].type==0) lazy[now][0].value=max(lazy[now][0].value,value);
else lazy[now][0].value=min(lazy[now][0].value,value);
}
else lazy[now].push_back({type,value});
}
else
{
if(lazy[now][0].type==0) // lazy[now][1].type은 1이다.
{
if(type==1) lazy[now][1].value=min(lazy[now][1].value,value);
else
{
if(value >= lazy[now][0].value) lazy[now][0]=lazy[now][1], lazy[now][1]={type,value};
else if(value >= lazy[now][1].value) lazy[now][0]=lazy[now][1], lazy[now][1]={type,value};
}
}
else // lazy[now][0].type은 1, lazy[now][1].type은 0이다.
{
if(type==0) lazy[now][1].value=max(lazy[now][1].value,value);
else
{
if(value <= lazy[now][0].value) lazy[now][0]=lazy[now][1], lazy[now][1]={type,value};
else if(value <= lazy[now][1].value) lazy[now][0]=lazy[now][1], lazy[now][1]={type,value};
}
}
}
}
void lazydown(int now,int now_l,int now_r)
{
for(int i=0;i<lazy[now].size();i++)
{
int type=lazy[now][i].type, value=lazy[now][i].value;
if(type==0) // 모든 값이 value 이상이 된다.
{
tree[now].Min=max(tree[now].Min,value);
tree[now].Max=max(tree[now].Max,value);
}
else // 모든 값이 value 이하가 된다.
{
tree[now].Max=min(tree[now].Max,value);
tree[now].Min=min(tree[now].Min,value);
}
if(now_l!=now_r)
{
check(type,value,now*2);
check(type,value,now*2+1);
}
}
lazy[now].clear();
}
void update(int l,int r,int type,int value,int now,int now_l,int now_r)
{
lazydown(now,now_l,now_r);
if(now_l>r || now_r<l) return;
else if(l<=now_l && now_r<=r)
{
check(type,value,now);
lazydown(now,now_l,now_r);
}
else
{
int mid=(now_l+now_r)/2;
update(l,r,type,value,now*2,now_l,mid);
update(l,r,type,value,now*2+1,mid+1,now_r);
tree[now].Max=max(tree[now*2].Max,tree[now*2+1].Max);
tree[now].Min=max(tree[now*2].Min,tree[now*2+1].Min);
}
}
void make_res(int now,int now_l,int now_r)
{
lazydown(now,now_l,now_r);
if(now_l==now_r) return;
int mid=(now_l+now_r)/2;
make_res(now*2,now_l,mid);
make_res(now*2+1,mid+1,now_r);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
for(int i=0;i<k;i++)
update(left[i]+1,right[i]+1,op[i]-1,height[i],1,1,base);
make_res(1,1,base);
for(int i=0;i<n;i++)
finalHeight[i]=tree[base+i].Min;
}
