svg_af's blog

Help with DZY loves Colors
By svg_af, history, 9 years ago, In English

Hello there

I'm trying to solve this problem but i can't seem to find the proper approach

I wasn't able to see the editorial's point of view either

if someone would kindly help me find a way to solve it that would be really appreciated!

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

»
9 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

You need to maintain two structures.

First one will simply store all intervals which are painted by same color. (Initially we have N such intervals)

Second structure will actually be simple segment tree with two operations:

  1. Add on an interval

  2. Get sum on an interval

When you need to process second type of queries, you simply ask the sum on an interval from your segment tree. This will work in per query

When you need to deal with first type, you iterate over all intervals these intersect with query's left and right border and add on an interval of segment tree, and replace these intervals with new color.

The trick is in that this process won't take O(N2) as you could initially think, this will work in because on each query of this type we either delete some intervals or add not more than two of them.

→ Reply