UKIEPC segment tree explanation

Revision en1, by grhkm, 2023-10-22 19:05:08

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!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English grhkm 2023-10-22 19:05:08 1281 Initial revision (published)