LogitechSellout's blog

How to solve segment tree problem, modification queries with a twist?
By LogitechSellout, history, 4 years ago, In English

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?

  • Vote: I like it
  • -6
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Fairly standard lazy propagation.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm not sure if you meant this solution, but I think a single normal segment tree is enough.

    Let us look at queries on a segment tree.

    When we query, we query a disjoint set of ranges, such that it covers all nodes in the range.

    When we update, we update a single element all the ranges that contain it.

    Now if we flip the purposes of the 2 functions, this can be done simply.

    For updating, we use the query function, and update all ranges and take minimum with val.

    When we query, we use the update function, and the answer is the minimum of a[i], and all the values in the ranges it is contained in.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I tried to do something like that but it gives WA, either my implementation is bad or simple segment tree doesn't work.

      My code snippet here: https://ideone.com/PaEJsU if anyone has time to debug

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -6 Vote: I do not like it

        At the very least, you could try coding something even resembling my idea. Why do you need to push here? Why is there a lazy array?

        Code

        According to me, your code is using lazy propogation, but it is not pushing on queries? I'm not sure what you have done.

        → Reply