Блог пользователя 3_Problems_Everyday

Автор 3_Problems_Everyday, история, 8 лет назад, По-английски

Could anyone please tell me how to solve Problem E . I have seen some codes which use a segment tree but i am not able to understand. Also there is no editorial for this round .Any help would be appreciated. Thanks in advance.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Hi, I've just solve this problem and looking for the editorial I found your question, maybe you already solves this problem but anyways.

I use a Segment Tree with Lazy Propagation, I don't know if it is the best solution, that's why I was looking for the editorial. If this technique is not familiar to you I suggest you to search it on google. Basically it allows to made updates in O(log(N)) time.

First, what you have to notice is that after each modification, you have to reset all the values, no matter what modifications occurred before. So if you know which was the last modification that affects the position you are analyzing you could answer the query. I let this part to you.

I used the ST to know latest modification. My ST answer the query max element in a range (in this particular problem the range is always length 1). Using lazy propagation you update range [y,y+k-1] whit value cont (the ordinal of the modification). When you ask for the max value you will get the desire ordinal of the modification.

I let you my code. 20223882 Sorry for my english.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I used another technique that is similar to this problem: 555B - Case of Fugitive. It's one that is used quite often in data structures problems. Try solving that one then solving this. I think it might give you some good insights. If you're desperate for the solution of this problem: 19610583