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!