How to solve segment tree problem, modification queries with a twist?

Revision en1, by LogitechSellout, 2020-09-05 22:40:50

This was inspired by http://www.usaco.org/index.php?page=viewproblem2&cpid=842

The problem statement is: Given an array $$$a$$$, you are given two types of queries. The first type asks you to query for a single element $$$a[i]$$$, The second type is of update type $$$(l,r,val)$$$, where all $$$a[i]$$$ such that $$$l<=i<=r$$$ are unchanged if $$$a[i]<=val$$$, and reduced to $$$val$$$ if $$$a[i]>val$$$. You can imagine that the array a is a head of hair with hair lengths $$$a[i]$$$ at position $$$i$$$, and you want to cut some given intervals to a given length

This can be easily solved offline — just sort the update queries in decreasing $$$val$$$ and it's a textbook segment tree problem (you can do this in the usaco). But how do you solve it online?

Tags #data structures, #segment tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English LogitechSellout 2020-09-05 22:40:50 800 Initial revision (published)