gs15120's blog

How can I solve this range quarry problem?
By gs15120, history, 4 years ago, In English

Let array a1,...,an, ( 1<= n <= 10^6 )

3 kinds of quarries, m in total ( 1<= m <= 10^6 )

1 l r k: add k to al, ..., ar

2 l r k: change ai ( l<= i <=r ) in to max( ai , k )

3 l r: print max( al, ... ,ar )

I think it could be done it at mlogn by segment tree. How can I?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it -17 Vote: I do not like it

Isn't this $$$\mathcal{O}(mn)$$$ anyway, if someone decides to just spam 3 1 n over and over and over again.

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

    You would have to print only the largest value, am I wrong?

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

      Ah, forgive me, I horribly misread. I thought it asked to print all the elements in the range, which is quite stupid of me tbh.

      Anyway, the comment of tfg should answer the question pretty well.

      → Reply
»
4 years ago, # |
  Vote: I like it +23 Vote: I do not like it

You're correct, you can do it better than quadratic. Read https://codeforces.net/blog/entry/57319, it's in there as task 2.

→ Reply