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] \geq 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 log^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 :
- Find out the location of the last zero.
- Add a delta in a range.
- 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))$.