Editorial : Ksyusha and the Loaded Set

H : Ksyusha and the Loaded Set can be solved using the tricks introduced in problem G: Penacony from last Div 3 Round. I talk more about the trick and the data structures used in this video

Define $dp[x]$ to be the longest streak of missing numbers starting at $x$. If a number is present in the set, you set $dp[x]$ to $0$. Otherwise, $dp[x]=1+dp[x+1]$. Hence, you can populate this DP right to left after reading the initial numbers.

To answer any query, you just need to find the first $x$ such that $dp[x]\ge k$.

When you add an element, you need to refresh the DP table to the left of $x$. You can iterate over each element, and check if $dp[i]>|x-i|$. If it is, you need to subtract $dp[x]$ from all such $i$. Finally, set $dp[x]=0$.

When you remove an element, you again need to refresh the DP table to the left of $x$. You set $dp[x]=dp[x+1]$. Then, for each element to the left, check if $x$ was a bottleneck for the streak, i.e, if $dp[i]==|x-i|$. If it is, you increment $dp[i]$ by $dp[x]$.

Code for $O(N^2)$.

Now, to optimize it to $\mathcal{O}(n\cdot lo{g}^2(n))$, we need to figure out how to refresh the DP table efficiently. First, notice that $dp$ values of missing streak would decrease by 1 each step until it falls to 0 and then it starts at a big number and keeps falling. Hence, in type 1 and type 2 queries, when we say that we need to refresh the DP table to the left, we only have to refresh the elements after the last $0$. Hence, we need a data structure that can efficiently :

1. Find out the location of the last zero.
2. Add a delta in a range.
3. Query maxima

Sadly, no such data structures exist. But we faced this same issue in G: Penacony from last Div 3 Round. Notice that 0 is always a minima. Hence, we can binary search on the left, and keep discarding one half of the range if the minima of that range is 0. Hence, a lazy segment tree from Atcoder Library suffices, usage of which I have discussed in the video above.

On second thought, you don’t even need to query min/max using Lazy segtree. The last $x$ where $dp[x]=0$ would simply be determined by finding the upper bound of existing elements and looking to the left. Hence, you just need a segment tree to do range increments and range maxima. So overall time complexity becomes $O(N\cdot log(N))$.

• Code
• Comment