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

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

Is there an algorithm like RMQ that we can change our array elements??? It means that we have an array with all the elements equal to 0 at first.(number of elements < 1e5) and we have 2 types of queries: 1-change the i'th value 2-give the minimum value in range [0, ri] (number of queries < 1e5) I'm new to programming and found nothing on the web I'll be glad if you help me tnx :) note that this is not the same as RMQ and our intervals start from 0!

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

»
10 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Maybe you're asking about simple segment tree. Try to google "minimum query segment tree" in google.

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

Finally an expert from AE. Congratulations sepanta. You have what you could not ever imagine ;)

»
10 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +6 Проголосовать: не нравится

everything I know is this contest must be unrated for sepanta that's really bad that you can earn ratings eeeeeasily in CF

»
10 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

Auto comment: topic has been updated by _VanGogh_ (previous revision, new revision, compare).

»
10 лет назад, скрыть # |
 
Проголосовать: нравится +7 Проголосовать: не нравится

Am I missing something?

»
10 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

Interest how this blog changed from reporting cheater to RMQ with BIT...

»
10 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

Yes you can use BIT for RMQ for intervals starting from 1st position, but why change your blog post from Cheater Report to this all of a sudden?
I hope CF has enough pages, so you can start this discussion in a separate post and avoid all the confusion people are going to face after reading the initial comments.

»
10 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

As far as I know, you can do this if the new value is less or equal to the previous stored value.