Hi, UKIEPC 2023 just concluded yesterday, the problems can be found here and the solutions can be found here.
I don't understand the solution to H. You should read the problems documentation linked above, but here is a short description. The problem asks for a data structure that supports two types of queries: (1) range add / sub (2) after removing duplicate consecutive elements of the array, check whether all "local minimas" of the array is strictly increasing, where "local minima" is defined as a[i] such that a[i — 1] > a[i] && a[i] < a[i + 1], ignoring the condition when out of bounds.
The solution says we can maintain a segment tree on the ranges of "increasing" and "non-increasing" sequences for the array. However, I am not sure what the segment tree should contain at all. Can someone provide a more detailed explanation? Any similar problems in the past (hopefully with writeup) will be great. I know the basic stuff about segment tree (range add range max etc.) and I want to understand the solution of this.
Thanks!
Before thinking about everything else, we must think about how to deal with merging duplicate elements. Well, to be exact, this can be done with a BBST, or simply
std::setin usual case. However, consider using a Splay Tree for this, so we can deal with this further into the solution.Onto the actual solution. Say, each nodes of a splay tree contains a segment (which are pairwise disjoint) and its value. If we range add on a segment $$$[L,R)$$$, there will be at most one segment that intersect with $$$L$$$, and at most one that intersect with $$$R$$$. These two segments will be "split" into two. The actual implementation of this is basically equivalent to inserting a node. Then, we range add on the segments which make up the segment $$$[L,R)$$$. Then afterwards, we merge the nodes that need to be merged. This "merging" only happens on $$$L$$$ and $$$R$$$ as well. So, to sum up, for each update we have $$$O(1)$$$ insertions, $$$O(1)$$$ deletions, $$$O(1)$$$ range update, $$$O(\log n)$$$ per operation. That is $$$O(\log n)$$$ in total.
Now for the local minimum check. Basically, notice in each update, the status of non-border segments do NOT change. The only thing that changes are the segments on the borders. That applies also to the status on whether a segment is a local minimum. So, maintain a Splay Tree containing local minimums. Then, determining whether a segment is sorted is not hard, you can basically just maintain adjacent differences, and the "is sorted?" query basically turns into RMQ. Time complexity follows that of the update query, which is $$$O(\log n)$$$.
I haven't looked at the official solution until this point, but I would guess that the gist should be almost the same. Hope this helped.