#include"wall.h"
#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
const int MAXN=2222222;
ii seg[MAXN*4];
bool lazy[MAXN*4];
int n;
ii merge(ii a,ii b)
{
ii c={max(a.fi,b.fi),min(a.se,b.se)};
if(c.fi>c.se)
{
if(a.fi<b.fi) return {c.fi,c.fi};
return {c.se,c.se};
}
return c;
}
void down(int pos)
{
seg[pos*2]=merge(seg[pos*2],seg[pos]);
seg[pos*2+1]=merge(seg[pos*2+1],seg[pos]);
seg[pos]={0,998244353};
}
void build(int l,int r,int pos)
{
if(l>r) return ;
seg[pos]={0,998244353};
if(l==r)
{
seg[pos]={0,0};
return ;
}
int mid=(l+r)/2;
build(l,mid,pos*2);
build(mid+1,r,pos*2+1);
}
void update(int l,int r,int u,int v,int ck,int val,int pos)
{
if(v<l||r<u) return ;
if(u<=l&&r<=v)
{
if(!ck) seg[pos]=merge(seg[pos],(ii){val,998244353});
else seg[pos]=merge(seg[pos],(ii){0,val});
return ;
}
int mid=(l+r)/2;
down(pos);
update(l,mid,u,v,ck,val,pos*2);
update(mid+1,r,u,v,ck,val,pos*2+1);
}
int get(int l,int r,int i,int pos)
{
if(l==r) return seg[pos].fi;
int mid=(l+r)/2;
down(pos);
if(i<=mid) return get(l,mid,i,pos*2);
return get(mid+1,r,i,pos*2+1);
}
void build_up(int l,int r,int t)
{
update(1,n,l+1,r+1,0,t,1);
}
void take_down(int l,int r,int t)
{
update(1,n,l+1,r+1,1,t,1);
}
int get_height(int i)
{
return get(1,n,i+1,1);
}
void buildWall(int N,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
n=N;
for(int i=0;i<k;i++) if(op[i]==1) build_up(left[i],right[i],height[i]);
else take_down(left[i],right[i],height[i]);
for(int i=0;i<n;i++) finalHeight[i]=get_height(i);
}
