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?
