Question on an Algorithm for Longest Increasing Subsequence

Question

I have been reading this paper: https://arxiv.org/abs/2011.10874

This paper presented an exact randomized algorithm with update time $\tilde{O}(n^{0.8})$. I will quickly talk about the overall idea of the paper: we first organizes elements by layers $L_i$ described as follows: "We define $b_i$ as the size of the longest increasing subsequence ending at element $a_i$ and divide the sequence into disjoint layers. More precisely, let each layer $L_i = \{a_j | b_j = i\}$ be the set of elements whose corresponding $b_j$ is equal to i. "

We then combine executive layers of equal size into basket (expect for the first and last basket). The baskets are considered light or heavy based on criteria listed in Page 14

I got quite confused with part of the algorithm when they say:

"Throughout our algorithm, we maintain a local data structure for each light basket i that stores the following information: If $i = 1$, then for each element ay of basket 1, we store the size of the longest increasing subsequence that ends at $a_y$. If $i > 1$, then for each boundary element $a_x$ of basket $i−1$ and each element $a_y$ of basket $i$, we store the size of the longest increasing subsequence that starts at $a_x$ and ends at $a_y$. Except for the initial element $a_x$, any element that may contribute to such a subsequence is certainly inside basket i" (Page 14).

The part that I am confused with is weather or not we dynamically change the number of layers in a basket. For example, if I remove the element "14" from the list, $L_8$ will only constitute "15", so should "15" be moved to Basket 3 or "15" is kept in Basket 4? This is pretty important since after the deletion, would "13" be the boundary term of Basket 3 or is it "15"?

Thanks

Update: I have understand the problem and post the resolution. I would like to keep the question for other users

Answer 1

Update:

I have thoroughly read through the paper myself and understand the problem better. So the algorithm fails if I make the above deletion (i.e. removing elements from a boundary layer). Layers $L_i = \{a_j | b_j = i\}$ are only for initialization, and for the duration of the algorithm, only the boundary layers are kept in tact to calculate one of the local data structure (which assumes the boundary layers are unchanged). This is a probabilistic algorithm and the paper show that we can get success rate to $1-n^{-10}$ after $20\log n$ repeats.