LLint's blog

Spoj Problem
By LLint, 11 years ago, In English

How to solve this problem

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Maybe you can use treap in segment tree?

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Here's one (maybe not an optimal) solution:
Let's imagine first that we have no update queries. Then the problem can be easily solved using SQRT-decomposition of queries (I think that's how it's done in the PewDiePie town called in English) and a map/unordered_map.
The solution is practically the same as the one described in this blog and has time asymptotic.
Now we need to handle update queries. Assume . Let's store update queries in an auxillary array in the sorted (by position) order. Now the idea is practically the same as above. We handle question queries as if there were no update but after we've inserted current segment in our DS we have to perform all necessary updates (there'll be no more than of them) in a straightforward way.
Of course, there's no such strange constraint as . But we can create it: just split all Q queries into blocks of and after we've handled a block we perform all updates from this block with our original array.
I hope it's right.

→ Reply